Submission #1499296
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
#define int long long
typedef long long ll;
typedef pair<ll,int>P;
vector<P>E[100000];
int a[100000],b[100000],c[100000];
ll d[100000];
ll nxt(ll p,ll a,ll b,ll c){
if(p<c)return c;
if((p-c)%(a+b)<a)return p;
return ((p-c)/(a+b)+1)*(a+b)+c;
}
signed main(){
int n,m,s,g;scanf("%lld%lld%lld%lld",&n,&m,&s,&g);s--;g--;
rep(i,n)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
rep(i,m){
int x,y,t;scanf("%lld%lld%lld",&x,&y,&t);x--;y--;
E[x].push_back(P(t,y));E[y].push_back(P(t,x));
}
priority_queue<P,vector<P>,greater<P>>que;
memset(d,0x3f,sizeof(d));d[s]=0;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();que.pop();
if(d[p.second]!=p.first)continue;
int e=nxt(p.first,a[p.second],b[p.second],c[p.second]);
for(P v:E[p.second]){
if(d[v.second]>e+v.first){
d[v.second]=e+v.first;que.push(P(d[v.second],v.second));
}
}
}
printf("%lld\n",d[g]);
}
Submission Info
Submission Time
2017-08-09 23:30:32+0900
Task
I - 信号待ち
User
autumn_eel
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
1004 Byte
Status
AC
Exec Time
87 ms
Memory
10880 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:18:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n,m,s,g;scanf("%lld%lld%lld%lld",&n,&m,&s,&g);s--;g--;
^
./Main.cpp:19:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,n)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
^
./Main.cpp:21:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int x,y,t;scanf("%lld%lld%lld",&x,&y,&t);x--;y--;
^
Judge Result
Set Name
All
Score / Max Score
100 / 100
Status
Set Name
Test Cases
All
00-sample1, 00-sample2, 00-small0, 00-small1, 00-small10, 00-small11, 00-small12, 00-small13, 00-small14, 00-small15, 00-small16, 00-small17, 00-small18, 00-small19, 00-small2, 00-small3, 00-small4, 00-small5, 00-small6, 00-small7, 00-small8, 00-small9, 20-large0, 20-large1, 20-large10, 20-large11, 20-large12, 20-large13, 20-large14, 20-large15, 20-large16, 20-large17, 20-large18, 20-large19, 20-large2, 20-large3, 20-large4, 20-large5, 20-large6, 20-large7, 20-large8, 20-large9, 50-corner00, 50-corner01, 50-corner02
Case Name
Status
Exec Time
Memory
00-sample1
AC
3 ms
4480 KB
00-sample2
AC
2 ms
4480 KB
00-small0
AC
2 ms
4480 KB
00-small1
AC
2 ms
4480 KB
00-small10
AC
7 ms
5376 KB
00-small11
AC
5 ms
5120 KB
00-small12
AC
7 ms
5376 KB
00-small13
AC
6 ms
5248 KB
00-small14
AC
5 ms
5120 KB
00-small15
AC
4 ms
4992 KB
00-small16
AC
5 ms
5120 KB
00-small17
AC
5 ms
5120 KB
00-small18
AC
4 ms
4736 KB
00-small19
AC
6 ms
5248 KB
00-small2
AC
2 ms
4480 KB
00-small3
AC
2 ms
4480 KB
00-small4
AC
2 ms
4480 KB
00-small5
AC
2 ms
4480 KB
00-small6
AC
2 ms
4480 KB
00-small7
AC
2 ms
4480 KB
00-small8
AC
2 ms
4480 KB
00-small9
AC
2 ms
4480 KB
20-large0
AC
85 ms
10880 KB
20-large1
AC
85 ms
10880 KB
20-large10
AC
84 ms
10880 KB
20-large11
AC
85 ms
10880 KB
20-large12
AC
85 ms
10880 KB
20-large13
AC
85 ms
10880 KB
20-large14
AC
85 ms
10880 KB
20-large15
AC
85 ms
10880 KB
20-large16
AC
84 ms
10880 KB
20-large17
AC
85 ms
10880 KB
20-large18
AC
85 ms
10880 KB
20-large19
AC
85 ms
10880 KB
20-large2
AC
85 ms
10880 KB
20-large3
AC
85 ms
10880 KB
20-large4
AC
85 ms
10880 KB
20-large5
AC
84 ms
10880 KB
20-large6
AC
85 ms
10880 KB
20-large7
AC
85 ms
10880 KB
20-large8
AC
87 ms
10880 KB
20-large9
AC
85 ms
10880 KB
50-corner00
AC
66 ms
10368 KB
50-corner01
AC
62 ms
10368 KB
50-corner02
AC
57 ms
10368 KB