Contest Duration: ~ (local time)

Submission #2808663

Source Code Expand

Copy
```#include <bits/stdc++.h>
#define N 1000000000000000
#define inf 10000000000000000
using namespace std;

typedef pair<int,int>P;
struct edge{
int req;
long long cost[2];
};
vector<edge> data[100005];
long long d[2][100005];
long long ans[100005];
long long n,m,t[2];
void dik(int check);

int main(){
long long i,j,k;
int a;
cin >> n >> m >> t[0] >> t[1];
for(i=0;i<m;++i){
edge x;
cin >> a >>x.req >> x.cost[0] >> x.cost[1];
data[a].push_back(x);
swap(a,x.req);
data[a].push_back(x);
}
dik(0);
dik(1);
//cout << n <<" "<< d[1][1];
/*for(j=0;j<2;++j){
for(i=1;i<=n;++i)cout << d[j][i] <<" ";
cout << endl;
}*/
ans[n+1]=inf;
for(j=n;j>=1;--j)ans[j]=min(ans[j+1],d[0][j]+d[1][j]);
for(i=1;i<=n;++i)cout << N-ans[i] << endl;
return 0;
}

void dik(int check){
priority_queue< P, vector<P> , greater<P> > qu;
fill(d[check],d[check]+n+1,inf);
d[check][t[check]]=0;
qu.push(P(0,t[check]));
while(!qu.empty()){
P p = qu.top();
qu.pop();
int  v = p.second;
if(d[check][v]<p.first)continue;
for(int i=0;i<data[v].size();++i){
edge e = data[v][i];
if(d[check][e.req]>d[check][v]+e.cost[check]){
d[check][e.req]=d[check][v]+e.cost[check];
qu.push(P(d[check][e.req],e.req));
}
}

}
}
```

#### Submission Info

Submission Time 2018-07-07 22:28:53+0900 D - Saving Snuuk m_tsubasa C++14 (GCC 5.4.1) 400 1352 Byte AC 535 ms 14820 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sampleRnd.txt, sampleT.txt
All 400 / 400 00yorimichi.txt, 11_0.txt, 11_1.txt, 11_2.txt, 11_3.txt, 11_4.txt, 1n1m1.txt, 1oo_0.txt, 1oo_1.txt, 1oo_2.txt, 1oo_3.txt, 1oo_4.txt, dangou_0.txt, dangou_1.txt, dangou_2.txt, dangou_3.txt, dangou_4.txt, edge.txt, high_0.txt, high_1.txt, high_2.txt, high_3.txt, high_4.txt, low_0.txt, low_1.txt, low_2.txt, low_3.txt, low_4.txt, oo1_0.txt, oo1_1.txt, oo1_2.txt, oo1_3.txt, oo1_4.txt, path_0.txt, path_1.txt, path_2.txt, path_3.txt, path_4.txt, path_5.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sampleRnd.txt, sampleT.txt, slast_0.txt, slast_1.txt, slast_2.txt, slast_3.txt, slast_4.txt, tlast_0.txt, tlast_1.txt, tlast_2.txt, tlast_3.txt, tlast_4.txt
Case Name Status Exec Time Memory
00yorimichi.txt 317 ms 12800 KB
11_0.txt 397 ms 12512 KB
11_1.txt 160 ms 11264 KB
11_2.txt 232 ms 11140 KB
11_3.txt 474 ms 13240 KB
11_4.txt 363 ms 12728 KB
1n1m1.txt 247 ms 11372 KB
1oo_0.txt 296 ms 12328 KB
1oo_1.txt 315 ms 12440 KB
1oo_2.txt 106 ms 9216 KB
1oo_3.txt 307 ms 12676 KB
1oo_4.txt 300 ms 12556 KB
dangou_0.txt 114 ms 9600 KB
dangou_1.txt 193 ms 10952 KB
dangou_2.txt 281 ms 11560 KB
dangou_3.txt 85 ms 7296 KB
dangou_4.txt 355 ms 13116 KB
edge.txt 348 ms 13056 KB
high_0.txt 124 ms 8192 KB
high_1.txt 149 ms 9856 KB
high_2.txt 363 ms 14820 KB
high_3.txt 20 ms 3968 KB
high_4.txt 275 ms 10432 KB
low_0.txt 88 ms 10880 KB
low_1.txt 94 ms 9600 KB
low_2.txt 260 ms 12136 KB
low_3.txt 230 ms 11168 KB
low_4.txt 155 ms 10580 KB
oo1_0.txt 309 ms 13072 KB
oo1_1.txt 280 ms 12392 KB
oo1_2.txt 227 ms 11584 KB
oo1_3.txt 145 ms 11008 KB
oo1_4.txt 224 ms 11728 KB
path_0.txt 280 ms 11648 KB
path_1.txt 280 ms 11648 KB
path_2.txt 134 ms 7296 KB
path_3.txt 172 ms 8448 KB
path_4.txt 95 ms 6016 KB
path_5.txt 262 ms 10624 KB
rnd_0.txt 411 ms 12508 KB
rnd_1.txt 535 ms 12960 KB
rnd_2.txt 38 ms 4480 KB
rnd_3.txt 514 ms 12820 KB
rnd_4.txt 197 ms 11368 KB
sampleRnd.txt 2 ms 2944 KB
sampleT.txt 2 ms 2944 KB
slast_0.txt 393 ms 12740 KB
slast_1.txt 132 ms 8960 KB
slast_2.txt 447 ms 12832 KB
slast_3.txt 252 ms 11612 KB
slast_4.txt 426 ms 12572 KB
tlast_0.txt 149 ms 10312 KB
tlast_1.txt 370 ms 12104 KB
tlast_2.txt 479 ms 13712 KB
tlast_3.txt 425 ms 13144 KB
tlast_4.txt 423 ms 13148 KB