差分约束
我也忘了谁说的了，反正我记得有人说过，只要是差分约束问题都可以转换成图
至少目前看来都是这样的
我一开始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\n",spfa());//} }