http://vijos.org/p/1082

非常有代表性的题目，在SPFA时多加一个判断即可

此题用SPFA有反例，正解搜索，此题解是错误的 (2016.11.27更改)

此问题可解所有体力+权值的最短路问题

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define ms(i,j) memset(i, j, sizeof(i));using namespace std;struct node{	int u;	int v;	int p;	int t;	node(int u1,int v1, int p1,int t1) : u(u1),v(v1),p(p1),t(t1) {}};const int maxn = 5000 + 2, maxm = 40000 + 2;vector
         
           a[maxm];int dis[maxn];int ex[maxn];int p[maxn];int n,m,s,t,k;queue
          
            q;int main () { scanf("%d%d", &n, &m); for (int i=1;i<=m;i++) { int x,y,c,d; scanf("%d%d%d%d", &x,&y,&c,&d); a[x].push_back(node(x,y,c,d)); a[y].push_back(node(y,x,c,d)); } scanf("%d%d%d", &s, &t, &k); //SPFA p[s] = k; ms(ex,false); ex[s]=true; ms(dis,27); dis[s]=0; dis[t]=100000000; q.push(s); while(!q.empty()) { int u = q.front();q.pop();ex[u]=false; for (int i=0;i
           
            dis[u]+pn.t&&p[u]>=pn.p) { dis[pn.v]=dis[u]+pn.t; p[pn.v] = p[u]-pn.p; if (!ex[pn.v]) { ex[pn.v] = true; q.push(pn.v); } } } } printf("%d\n", (dis[t]==100000000) ? -1 : dis[t]); return 0;}