# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
36229 | 2017-12-06T11:48:03 Z | Flumen | Price List (POI13_cen) | C++11 | 143 ms | 10660 KB |
#include<bits/stdc++.h> using namespace std; vector<pair<int,int> >node[100100]; int ans[100100],mark[100100]; queue<pair<int,int> >Q; priority_queue<pair<int,int> >X; void d(int k,int b){ int i; Q.push(make_pair(k,0)); while(!Q.empty()){ mark[Q.front().first]=1; for(i=0;i<node[Q.front().first].size();i++){ if(mark[node[Q.front().first][i].first])continue; mark[node[Q.front().first][i].first]=1; Q.push(make_pair(node[Q.front().first][i].first,Q.front().first)); if(Q.front().second!=0){ node[node[Q.front().first][i].first].push_back(make_pair(Q.front().second,b)); node[Q.front().second].push_back(make_pair(node[Q.front().first][i].first,b)); } } Q.pop(); } } void dij(int k){ int i,x,y; X.push(make_pair(0,k)); while(!X.empty()){ x=X.top().second; y=X.top().first; X.pop(); if(mark[x])continue; mark[x]=1; ans[x]=y*-1; for(i=0;i<node[x].size();i++){ if(mark[node[x][i].first])continue; X.push(make_pair(y-node[x][i].second,node[x][i].first)); } } } int main(){ int n,m,k,a,b,i,x,y; scanf("%d%d%d%d%d",&n,&m,&k,&a,&b); for(i=0;i<m;i++) { scanf("%d%d",&x,&y); node[x].push_back(make_pair(y,a)); node[y].push_back(make_pair(x,a)); } d(k,b); for(i=1;i<=n;i++)mark[i]=0; dij(k); for(i=1;i<=n;i++)printf("%d\n",ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5148 KB | Output is correct |
2 | Correct | 0 ms | 5148 KB | Output is correct |
3 | Correct | 0 ms | 5148 KB | Output is correct |
4 | Incorrect | 3 ms | 5148 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 5148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 5148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 ms | 5848 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 43 ms | 7860 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 73 ms | 9176 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 139 ms | 9748 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 143 ms | 10660 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 126 ms | 9968 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 123 ms | 9900 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |