/* - - 这题做了一天.....粗心害死人啊 题目描述恶心 数据更恶心... 先处理一下能走的边 能走的点（到这建边从终点跑一下.） 然后就是SPFA了 注意负环的判断 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define maxn 1110 #define maxm 10010 #define inf 999999999 using namespace std; int n,m,num,num2,head[maxn],s,t,vis[maxm]; int ans[maxm],size,f[maxn],falg,Dis[maxn],Ti[maxn];//ans存能走的边 并不是一个点对应一条边 要用maxm！ int sum[maxn],can[maxn],head2[maxn]; struct node { int u,v,ti,si,pre; }e[maxm],e2[maxm]; queue<int>q; int init() { int x=0;char s;bool f=0;s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} if(f)return -x;else return x; } void Add(int from,int to,int cost,int len) { num++; e[num].u=from; e[num].v=to; e[num].si=len; e[num].ti=cost; e[num].pre=head[from]; head[from]=num; } void Add2(int from,int to,int cost,int len) { num2++; e2[num2].u=from; e2[num2].v=to; e2[num2].si=len; e2[num2].ti=cost; e2[num2].pre=head2[from]; head2[from]=num2; } void Edge_can()//能走的边 { for(int i=0;i<=n;i++) { int minn=inf,k; for(int j=head[i];j;j=e[j].pre) if(e[j].ti<minn) minn=e[j].ti; for(int j=head[i];j;j=e[j].pre) if(e[j].ti==minn) ans[++size]=j; } for(int i=1;i<=size;i++)vis[ans[i]]=1; } void Bfs(int x) { queue<int>qi; qi.push(x); can[x]=1; while(!qi.empty()) { int k=qi.front(); qi.pop(); for(int i=head2[k];i;i=e2[i].pre) if(can[e2[i].v]==0) { qi.push(e2[i].v); can[e2[i].v]=1; } } } void Point_can()//到这建边搜能走的点 { for(int i=1;i<=num;i++) if(vis[i]) Add2(e[i].v,e[i].u,e[i].ti,e[i].si); Bfs(t); } void SPFA(int st) { q.push(st); f[st]=1; sum[st]++; Dis[st]=0; Ti[st]=0; while(!q.empty()) { int now=q.front(); q.pop(); f[now]=0; if(sum[now]>n+5)//负环死循环 { falg=1; break; } for(int i=head[now];i;i=e[i].pre) if((Ti[now]+e[i].ti<Ti[e[i].v]||(Ti[now]+e[i].ti==Ti[e[i].v]&& Dis[now]+e[i].si<Dis[e[i].v]))&&vis[i]&&can[e[i].v])//没有 f[e[i].v]==0 !!! { Ti[e[i].v]=Ti[now]+e[i].ti; Dis[e[i].v]=Dis[now]+e[i].si; if(f[e[i].v]==0) { q.push(e[i].v); f[e[i].v]=1; sum[e[i].v]=sum[now]+1; } } } } int main() { while(~scanf("%d%d%d%d",&n,&m,&s,&t)) { n--; memset(head,0,sizeof(head));memset(ans,0,sizeof(ans));//多组数据....注意初始化 memset(vis,0,sizeof(vis));memset(can,0,sizeof(can)); memset(f,0,sizeof(f));memset(sum,0,sizeof(sum)); memset(Dis,127/3,sizeof(Dis));memset(Ti,127/3,sizeof(Ti)); memset(head2,0,sizeof(head2)); size=0;num=0;falg=0;num2=0; int ui,vi,dis,cost1,cost2; for(int i=1;i<=m;i++) { ui=init(); vi=init(); cost1=init(); dis=init(); cost2=init(); Add(ui,vi,cost1,dis); Add(vi,ui,cost2,dis); } Edge_can(); Point_can(); if(can[s]==0)//跑不到终点 { printf("VOID "); continue; } SPFA(s); if(falg==1)printf("UNBOUND ");//能跑到 并且有负环 if(falg==0)printf("%d %d ",Ti[t],Dis[t]); } return 0; }