| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1084291 | 2024-09-05T18:40:35 Z | vjudge1 | 악어의 지하 도시 (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]<<" ";
}