# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1084291 | 2024-09-05T18:40:35 Z | vjudge1 | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#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]<<" "; }