第一道差分约束
题意：熊孩纸系列…………
A认为B不会比他多c颗糖及
candies[B] <= candies[A] + C
与d[v] <= d[u] + e.cost 类似
#include <iostream> #include <vector> #include <stack> #include <cstring> #include <cstdio> using namespace std; #define INF 1<<30 #define MAX_V 50000 #define MAX_E 300000 struct edge{ int v; int cost; int next; }; struct edge es[MAX_E]; int head[MAX_V]; int len = 0; void add(int from,int to,int val) { es[len].v=to; es[len].cost =val; es[len].next = head[from]; head[from]=len++; } int V; bool inqueue[MAX_V]; int d[MAX_V]; void spfa(int s){ for (int i = 0;i<=V;i++) d[i] = INF; memset(inqueue,0,sizeof inqueue); d[s] = 0; inqueue[s] = true; stack<int> Q; Q.push(s); while (!Q.empty()){ int u = Q.top(); Q.pop(); inqueue[u] = false; for (int i = head[u];i != -1;i = es[i].next){ int v = es[i].v; if (d[v] > d[u] + es[i].cost){ d[v] = d[u] + es[i].cost; if (!inqueue[v]){ Q.push(v); inqueue[v] = true; } } } } } void init(){ int M; scanf("%d%d",&V,&M); memset(head,-1,sizeof head); for (int i = 0;i<M;i++){ int from,to,val; scanf("%d%d%d",&from,&to,&val); add(from,to,val); } } int main() { init(); spfa(1); printf("%d\n",d[V]); return 0; }