Submission #1499290
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
vector<P>E[100000];
int a[100000],b[100000],c[100000];
int 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;
}
int main(){
int n,m,s,g;scanf("%d%d%d%d",&n,&m,&s,&g);s--;g--;
rep(i,n)scanf("%d%d%d",&a[i],&b[i],&c[i]);
rep(i,m){
int x,y,t;scanf("%d%d%d",&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:28:58+0900
Task
I - 信号待ち
User
autumn_eel
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
959 Byte
Status
WA
Exec Time
71 ms
Memory
9344 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:36:22: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int’ [-Wformat=]
printf("%lld\n",d[g]);
^
./Main.cpp:17:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n,m,s,g;scanf("%d%d%d%d",&n,&m,&s,&g);s--;g--;
^
./Main.cpp:18:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,n)scanf("%d%d%d",&a[i],&b[i],&c[i]);
^
./Main.cpp:20:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int x,y,t;scanf("%d%d%d",&x,&y,&t);x--;y--;
^
Judge Result
Set Name
All
Score / Max Score
0 / 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
2944 KB
00-sample2
AC
3 ms
2944 KB
00-small0
AC
3 ms
2944 KB
00-small1
WA
3 ms
2944 KB
00-small10
AC
8 ms
3840 KB
00-small11
AC
5 ms
3584 KB
00-small12
AC
8 ms
3840 KB
00-small13
AC
7 ms
3840 KB
00-small14
AC
6 ms
3712 KB
00-small15
AC
5 ms
3584 KB
00-small16
AC
6 ms
3712 KB
00-small17
AC
6 ms
3712 KB
00-small18
AC
4 ms
3200 KB
00-small19
AC
6 ms
3712 KB
00-small2
AC
2 ms
2944 KB
00-small3
WA
3 ms
2944 KB
00-small4
AC
3 ms
2944 KB
00-small5
AC
2 ms
2944 KB
00-small6
AC
3 ms
2944 KB
00-small7
WA
3 ms
2944 KB
00-small8
WA
3 ms
2944 KB
00-small9
WA
2 ms
2944 KB
20-large0
WA
71 ms
9216 KB
20-large1
WA
70 ms
9216 KB
20-large10
WA
70 ms
9216 KB
20-large11
WA
71 ms
9216 KB
20-large12
WA
71 ms
9216 KB
20-large13
WA
71 ms
9344 KB
20-large14
WA
71 ms
9216 KB
20-large15
WA
71 ms
9216 KB
20-large16
WA
70 ms
9216 KB
20-large17
WA
71 ms
9344 KB
20-large18
WA
71 ms
9344 KB
20-large19
WA
71 ms
9216 KB
20-large2
WA
71 ms
9344 KB
20-large3
WA
71 ms
9216 KB
20-large4
WA
70 ms
9216 KB
20-large5
WA
70 ms
9216 KB
20-large6
WA
71 ms
9216 KB
20-large7
WA
71 ms
9344 KB
20-large8
WA
71 ms
9344 KB
20-large9
WA
70 ms
9216 KB
50-corner00
WA
65 ms
8832 KB
50-corner01
WA
61 ms
8832 KB
50-corner02
WA
57 ms
8832 KB