# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1084291 | vjudge1 | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define inf 1e9+1
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
struct node{
int nod,cost;
bool operator >(const node b) const {
return cost>b.cost;
}
};
vector<vector<node> > G;
int n,m,x,y,c,st,d[10001];
void dij(int start){
for(int i=1;i<=n;i++) d[i]=inf;
priority_queue<node,vector<node>,greater<node> > pq;
pq.push({start,0});
d[start]=0;
while(!pq.empty()){
node x=pq.top();
pq.pop();
for(auto vec:G[x.nod]){
if(d[vec.nod]>d[x.nod]+vec.cost)
{
d[vec.nod]=d[x.nod]+vec.cost;
pq.push({vec.nod,d[vec.nod]});
}
}
}
}
int main()
{
fin>>n>>m;
G.resize(n+1);
for(int i=1;i<=m;i++){
fin>>x>>y>>c;
G[x].push_back({y,c});
G[y].push_back({x,c});
}
fin>>st;
dij(st);
for(int i=1;i<=n;i++)
cout<<d[i]<<" ";
}