Submission #2813641
Source Code Expand
#include<cstdio> #include<queue> #include<utility> #include<cstring> #include<stack> #include<algorithm> #include<cmath> #include<iostream> #include<vector> using namespace std; #define MAX_N 100001 #define INF 10E15 + 1 #define REP(i,COUNT) for(int i=0;i<(int)(COUNT);i++) struct edge{ long long int to, cost; }; typedef vector<vector<edge> > AdjList; AdjList graph; AdjList graph2; typedef pair<long long int, long long int> P; void init(int n); int find(int n); void unite(int x,int y); bool same(int x, int y); int dx[4] = {1,0,0,-1}; int dy[4] = {0,1,-1,0}; vector<long long int> dist; void dijkstra(int n,long long int s){ dist = vector<long long int>(n,INF); dist[s] = 0; priority_queue<P, vector<P> , greater<P> > que; que.push(P(0,s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(dist[v] < p.first) continue; REP(i,graph[v].size()){ edge e = graph[v][i]; if(dist[e.to] > dist[v] + e.cost){ dist[e.to] = dist[v] + e.cost; que.push(P(dist[e.to],e.to)); } } } } int main() { long long int money = 1.0E15,res[100001]; long long int u,v,n,m,s,t,a,b,distt[100001]; cin >> n >> m >> s >> t; graph = AdjList(n); graph2 = AdjList(n); REP(i,m){ cin >> u >> v >> a >> b; graph[u-1].push_back((edge){v-1,a}); graph[v-1].push_back((edge){u-1,a}); graph2[u-1].push_back((edge){v-1,b}); graph2[v-1].push_back((edge){u-1,b}); } dijkstra(n,s-1); REP(i,n)distt[i] = dist[i]; graph = graph2; dijkstra(n,t-1); res[n-1] = distt[n-1] + dist[n-1]; for(int i=n-2;i>=0;i--) res[i] = min(distt[i] + dist[i],res[i+1]); REP(i,n) cout << money - res[i] << endl; return 0; } int par[MAX_N]; int ranks[MAX_N]; //n要素で初期化 void init(int n){ REP(i,n){ par[i] = i; ranks[i] = 0; } } //木の根を求める int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } void unite(int x,int y){ x = find(x); y = find(y); if(x == y) return ; if(ranks[x] < ranks[y]){ par[x] = y; }else{ par[y] = x; if(ranks[x] == ranks[y]) ranks[x]++; } } bool same(int x, int y){ return find(x) == find(y); }
Submission Info
Submission Time | |
---|---|
Task | D - Saving Snuuk |
User | makss |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2341 Byte |
Status | AC |
Exec Time | 371 ms |
Memory | 19364 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sampleRnd.txt, sampleT.txt |
All | 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 | AC | 326 ms | 18160 KB |
11_0.txt | AC | 296 ms | 15760 KB |
11_1.txt | AC | 161 ms | 11704 KB |
11_2.txt | AC | 201 ms | 11972 KB |
11_3.txt | AC | 369 ms | 19236 KB |
11_4.txt | AC | 322 ms | 16832 KB |
1n1m1.txt | AC | 250 ms | 14664 KB |
1oo_0.txt | AC | 259 ms | 15296 KB |
1oo_1.txt | AC | 275 ms | 15760 KB |
1oo_2.txt | AC | 107 ms | 8576 KB |
1oo_3.txt | AC | 283 ms | 16348 KB |
1oo_4.txt | AC | 274 ms | 15756 KB |
dangou_0.txt | AC | 116 ms | 9216 KB |
dangou_1.txt | AC | 207 ms | 11888 KB |
dangou_2.txt | AC | 295 ms | 16356 KB |
dangou_3.txt | AC | 86 ms | 6312 KB |
dangou_4.txt | AC | 364 ms | 19068 KB |
edge.txt | AC | 340 ms | 18928 KB |
high_0.txt | AC | 116 ms | 7684 KB |
high_1.txt | AC | 146 ms | 9984 KB |
high_2.txt | AC | 344 ms | 18616 KB |
high_3.txt | AC | 20 ms | 1792 KB |
high_4.txt | AC | 266 ms | 14132 KB |
low_0.txt | AC | 93 ms | 11008 KB |
low_1.txt | AC | 99 ms | 9336 KB |
low_2.txt | AC | 269 ms | 17164 KB |
low_3.txt | AC | 243 ms | 15448 KB |
low_4.txt | AC | 166 ms | 11700 KB |
oo1_0.txt | AC | 292 ms | 17780 KB |
oo1_1.txt | AC | 236 ms | 14500 KB |
oo1_2.txt | AC | 198 ms | 12712 KB |
oo1_3.txt | AC | 149 ms | 11520 KB |
oo1_4.txt | AC | 194 ms | 12480 KB |
path_0.txt | AC | 293 ms | 16228 KB |
path_1.txt | AC | 293 ms | 16100 KB |
path_2.txt | AC | 140 ms | 8120 KB |
path_3.txt | AC | 178 ms | 10084 KB |
path_4.txt | AC | 99 ms | 5660 KB |
path_5.txt | AC | 256 ms | 14136 KB |
rnd_0.txt | AC | 294 ms | 15608 KB |
rnd_1.txt | AC | 347 ms | 18844 KB |
rnd_2.txt | AC | 37 ms | 2432 KB |
rnd_3.txt | AC | 328 ms | 17980 KB |
rnd_4.txt | AC | 210 ms | 12484 KB |
sampleRnd.txt | AC | 1 ms | 256 KB |
sampleT.txt | AC | 1 ms | 256 KB |
slast_0.txt | AC | 287 ms | 15232 KB |
slast_1.txt | AC | 134 ms | 8192 KB |
slast_2.txt | AC | 348 ms | 18596 KB |
slast_3.txt | AC | 224 ms | 12792 KB |
slast_4.txt | AC | 305 ms | 16228 KB |
tlast_0.txt | AC | 155 ms | 10564 KB |
tlast_1.txt | AC | 264 ms | 14504 KB |
tlast_2.txt | AC | 333 ms | 18232 KB |
tlast_3.txt | AC | 371 ms | 19364 KB |
tlast_4.txt | AC | 357 ms | 19364 KB |