新鲜事
原文
最短路：（dijistra、spfa）void dijistra(int rt){ priority_queue<Node> q; dis[rt]=0; bool vis[N]={false}; q.push((Node){rt,0}); while(!q.empty()) { int u=q.top().u; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].dis) { dis[v]=dis[u]+edge[i].dis; q.push((Node){v,dis[v]}); } } }}void spfa(){ for(int i=1;i<=n;++i) { exist[i]=0; dis[i]=2147483647; } queue<int> que; que.push(start); exist[start]=1; dis[start]=0; while(!que.empty()) { int u=que.front(); que.pop();exist[u]=0; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w; if(!exist[v]) { exist[v]=1; que.push(v); } } } }}
