填个坑。
因为之前一直用spfa,导致没写过dijstra,最近写了3个题全WA了,最后发现是dij的坑没填上hhh,和spfa完全混了。
提供代码,自认为可读性挺高,需要的直接cv拿走。
#include<cstdio> #include<cstring> #include<iostream> #include<queue> #define N 10005 #define ll long long using namespace std; int read() { int ans=0; char ch=getchar(),last=' '; while(ch>'9'||ch<'0')last=ch,ch=getchar(); while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); return last=='-'?-ans:ans; } int n,m,num,u,v,w,s; int hea[N],vis[N],dis[N]; struct edg{ int nex,to,dis; }edge[500006]; struct node{ int num,dis; bool operator < (const node& b)const{ return dis>b.dis; } }; inline void add(int from,int to,int dis) { num++; edge[num].dis=dis; edge[num].nex=hea[from]; edge[num].to=to; hea[from]=num; } void dij(int s) { for(int i=1;i<=n;i++) { dis[i]=2147483647; } memset(vis,0,sizeof(vis)); dis[s]=0; priority_queue<node> q; q.push((node){s,0}); while(!q.empty()) { node kk=q.top();q.pop(); int now=kk.num; if(vis[now]==1)continue; vis[now]=1; for(int i=hea[now];i;i=edge[i].nex) { int v=edge[i].to; if(dis[v]>dis[now]+edge[i].dis) { dis[v]=dis[now]+edge[i].dis; q.push((node){v,dis[v]}); } } } } int main(){ n=read(),m=read(),s=read(); for(int i=1;i<=m;i++) { u=read(),v=read(),w=read(); add(u,v,w); } dij(s); for(int i=1;i<=n;i++) { printf("%d ",dis[i]); } return 0; }
NOIP考试时如果没让你判负环千万记得用堆优化dijstra,卡spfa是出题人日常操作。