求所謂的 optimal path:
對某個頂點,只能沿著它所有出邊中weight最小的那些路走;
從起點到終點的總weight最小;
如果有weight相同的,取總length最短的.
可能有負環(huán),自環(huán),平行邊.

先將不符合要求的邊刪掉.
接著,關鍵在于如何判斷有效負環(huán),即該負環(huán)處在起點到終點的路上.
實際上,只用保留原圖中從起點能到達,并且能到達終點的頂點.
如果用標準bellman-ford,需要2次DFS:從起點開始沿邊的方向DFS,標記能到達的點;從終點開始沿邊的逆向DFS,標記點.
2次都被標記到的點,才是實際有效點.將剩余點刪掉.
如果用SPFA,只用執(zhí)行逆向DFS,因為SPFA本身的擴展是從起點開始沿正向搜索擴展的.
可以建個新圖,回避刪邊刪點的麻煩.

無法到達,輸出VOID:之前從終點開始的DFS無法到達起點
weight無下界,輸出UNBOUND:新圖中存在關于weight的負環(huán)
要注意松弛操作weight的優(yōu)先級最高...我居然犯這么低級的錯誤.
最后若有界解存在,輸出wi[B]和di[B]

ps. 如果這題改成: 求length最短的路徑中,weight最小的路徑,就不一樣了,得判斷負環(huán)是不是在起點到終點的必經(jīng)之路上,如果不是,還要不斷走負環(huán),使得在lenght最短的前提下,weight取盡量大.

  1#include <iostream>
  2using namespace std;
  3
  4const int MAXQ = 65536;
  5const int INF = -0x7fffffff;
  6
  7struct EDGE{
  8    int v,e,w,l;
  9}edg[5100*8];
 10int se, gt[1100],gg[1100]; //原圖,新圖 
 11int cn[1100], re[1100], di[1100],wi[1100]; //頂點入列次數(shù), 頂點rewarding邊權, dist, weight 
 12bool ok[1100],inq[1100]; //能否到達終點, 是否在隊列中 
 13int que[MAXQ],pq,sq;
 14int ansW,ansL;
 15int N,M,A,B;
 16
 17inline void addedge(int u, int v, int w, int l, int g[]){
 18    edg[se].v = v;
 19    edg[se].w = w;
 20    edg[se].l = l;
 21    edg[se].e = g[u];
 22    g[u] = se++;
 23}
 24
 25inline void skp(char c){
 26    while(getchar()!=c);
 27}
 28
 29bool input(){
 30    int i,j,k,u,v,wf,wb,l;
 31    se = 2;
 32    memset(gt, 0, sizeof(gt));
 33    memset(gg, 0, sizeof(gg));
 34    memset(re, 0x7f, sizeof(re));
 35    if(scanf("%d%d",&N,&M)==EOF) return false;
 36    scanf("%d%d",&A,&B);
 37    for(i=0; i<M; i++){
 38        skp('('); scanf("%d",&u);
 39        skp(','); scanf("%d",&v);
 40        skp(','); scanf("%d",&wf);
 41        skp('['); scanf("%d",&l);
 42        skp(']'); scanf("%d",&wb);
 43        skp(')');
 44        addedge(u,v,wf,l,gt);
 45        addedge(v,u,wb,l,gt);
 46        re[u] = min(re[u], wf);
 47        re[v] = min(re[v], wb);
 48    }
 49    return true;
 50}
 51
 52void dfs(int r){ //從B開始沿反向邊遍歷 
 53    int i,j,k;
 54    ok[r]=true;
 55    for(j=gt[r]; j>0; j=edg[j].e){
 56        if(ok[edg[j].v]==true) continue;
 57        if(edg[j^1].w == re[edg[j].v])
 58            dfs(edg[j].v);
 59    }
 60}
 61
 62
 63bool spfa(){
 64    int i,j,k,u,v,w;
 65    bool flag;
 66    memset(cn, 0, sizeof(cn)); //入列次數(shù) 
 67    for(i=0; i<N; i++){
 68        di[i] = wi[i] = INF;
 69    }
 70    memset(inq, false, sizeof(inq)); //是否在隊列中 
 71    pq = sq = 0;
 72    que[sq++] = A;
 73    di[A] = 0; wi[A] = 0;
 74    while(pq!=sq){
 75        u = que[pq]; inq[u]=false;
 76        if(++pq == MAXQ) pq=0;
 77        for(j=gg[u]; j>0; j=edg[j].e){
 78            v = edg[j].v; flag = false; //是否有松弛操作 
 79            if(wi[v] == INF || wi[v]>wi[u]+edg[j].w){ //對weight,優(yōu)先級最高 
 80                flag=true;
 81                wi[v] = wi[u]+edg[j].w;
 82                di[v] = di[u]+edg[j].l;
 83                if(inq[v]==false && ++cn[v]>N*2) //判斷負環(huán) 
 84                    return false;
 85            }
 86            else if(wi[v]==wi[u]+edg[j].w){
 87                if(di[v] == INF || di[v]>di[u]+edg[j].l){ //對length 
 88                    flag=true;
 89                    di[v] = di[u]+edg[j].l;
 90                }
 91            }
 92            if(inq[v]==false && flag==true){
 93                inq[v]=true;
 94                que[sq] = v;
 95                if(++sq == MAXQ) sq=0;
 96            }
 97        }
 98    }
 99    ansW = wi[B];
100    ansL = di[B];
101    return true;
102}
103
104
105void solve(){
106    int i,j,k;
107    
108    memset(ok,false,sizeof(ok));
109    dfs(B);
110    if(ok[A]==false){
111        puts("VOID"); return ;
112    }
113    for(i=0; i<N; i++){ //建新圖 
114        if(ok[i]==false) continue;
115        for(j=gt[i]; j>0; j=edg[j].e){
116            if(edg[j].w == re[i] && ok[edg[j].v]==true){
117                addedge(i, edg[j].v, edg[j].w, edg[j].l, gg);
118                //printf("%d,%d(%d,%d) ",i,edg[j].v,edg[j].w,edg[j].l);
119            }
120        }
121    }
122    ansL = ansW = 0x7fffffff;
123    if(spfa()==false){
124        puts("UNBOUND"); return ;
125    }
126    printf("%d %d\n",ansW,ansL);
127}
128    
129
130int main(){
131    while(input()){
132        solve();
133    }
134    return 0;
135}