spfa会被卡 试试dijskstra
没想到这个题写了 2h 结果是读入优化写错了
rio
#include#include #include #include #include #include #define maxn 500010 #define maxx 500010#define inf 2147483647using namespace std;//typedef pair pa;//priority_queue ,greater >q;priority_queue< pair > q;int n,head[maxx];long long dis[maxx];int vis[maxx];int m,s,cnt;void read(int &x){ x=0;int flag=1;char c=getchar(); while(c<'0'||c>'9') flag=(c=='-'?-1:1),c=getchar(); while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); x=x*flag;}struct Edge{ int u,v; long long w;}edge[maxn];void add(int u,int v,long long w){ //nex edge[++cnt].v=v;//to edge[cnt].w=w;//v edge[cnt].u=head[u]; head[u]=cnt;//fr}void dijs(){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=inf; dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()){ int now=q.top().second;q.pop(); if(vis[now]) continue; vis[now]=1; for(int i=head[now];i;i=edge[i].u){ int v=edge[i].v; if(dis[v]>dis[now]+edge[i].w) { dis[v]=dis[now]+edge[i].w; q.push(make_pair(-dis[v],v)); } } }} int main(){ read(n);read(m);read(s); for(int i=1;i<=m;i++){ int u,v,w; read(u);read(v);read(w); add(u,v,w); } dijs(); for(int i=1;i<=n;i++) cout< <<" ";}