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
Task D - Saving Snuuk
User m_tsubasa
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1352 Byte
Status
Exec Time 535 ms
Memory 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