最短路~spfa模板

#include<iostream> #include<cstdio> #include<algorithm> #include<memory.h> #include<cmath> #include<queue> #define oo 2147483647 using namespace std; int v[n]; bool vis[n]; int dis[n]; int num; struct my {int x,y,l,ne;}e[m]; queue<int>q; void put(int x,int y,int l) { num++; e[num].x=x; e[num].y=y; e[num].l=l; e[num].ne=v[x]; v[x]=num; } void spfa() { memset(vis,false,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); vis[S]=1; dis[S]=0; q.push(S); while(!q.empty()) { int x=q.front(); vis[x]=0; q.pop(); for(int i=v[x];i;i=e[i].ne) { int y=e[i].y; if(dis[y]>dis[x]+e[i].l) { dis[y]=dis[x]+e[i].l; if(!vis[y]) { q.push(y); vis[y]=1; } } } } vis[x]=0; }