本来我写的对的
我就多手写了个
ios::sync_with_stdio(false);
我程序里面用了cin 还有scanf 本来想偷偷懒
我就说 我查了半天错 根本找不到的啊...
后来交了几次 发现一直有RE 才发现...... 我好笨
//最短路 dijkstral
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
const ll INF = ;
typedef pair<ll ,int> pli;
struct node
{
int to,cost;
node(int t,int c):to(t),cost(c){}
bool operator < (const node & a)const {
return cost > a.cost;
}
};
vector<node> E[maxn];
ll d[maxn];
priority_queue<pli,vector<pli>,greater<pli> > Q; int main()
{ int n,m,st;
cin>> n>>m>>st;
for(int i=;i<=m;i++)
{
int x,y,v;
scanf("%d %d %d",&x, &y ,&v);
E[x].push_back({y,v});
}
for(int i=;i<=n;i++)
{
d[i]=INF;
}
d[st] = ;
Q.push({,st});
while ( Q.size() )
{
pli now = Q.top();Q.pop();
ll cost = now.first;
int p=now.second;
if(cost >= INF)
continue;
for(int i=;i<E[p].size();i++)
{
int v = E[p][i].to;
if(d[v] > cost + E[p][i].cost)
{
d[v] = cost + E[p][i].cost;//更新最短路；
Q.push({d[v],v});
}
}
}
for(int i=;i<=n;i++)
{
if(i!= n)
cout<<d[i]<<" ";
else
cout<<d[i];
}
cout<<endl; }