poj 3159
差分约束
我也忘了谁说的了，反正我记得有人说过，只要是差分约束问题都可以转换成图
至少目前看来都是这样的
我一开始spfa+queue超时
看别人博客才知道要用spfa+stack，感觉智商又下降了一点
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int maxn = 30005; int head[maxn]; int nex[150005]; int cnt; int dis[maxn]; bool vis[maxn]; struct node { int v; int w; }; node mp[150005]; int n,m; void adde(int a,int b,int c) { mp[cnt].v = b; mp[cnt].w = c; nex[cnt] = head[a]; head[a] = cnt++; } long long spfa() { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); int stac[maxn]; int top = 0; stac[top++] = 1; dis[1] = 0; vis[1] =true; while(top) { int u = stac[--top]; vis[u] = false; for(int i = head[u]; i != -1; i = nex[i]) { //cout << u << " " << mp[i].v << " " << mp[i].w << endl; if(dis[mp[i].v] > dis[u] + mp[i].w) { dis[mp[i].v] = dis[u] + mp[i].w; //cout<< mp[i].v << " " << dis[mp[i].v] << endl; if(vis[mp[i].v] == false) { stac[top++] = mp[i].v; vis[mp[i].v] = true; } } } } return dis[n]; } int main() { //while(scanf("%d%d",&n,&m) != EOF) //{ memset(mp,0,sizeof(mp)); scanf("%d%d",&n,&m); cnt = 0; memset(head,-1,sizeof(head)); for(int i = 0; i < m; ++i) { int a,b,c; scanf("%d%d%d",&a,&b,&c); adde(a,b,c); } printf("%d ",spfa()); //} }