一开始重新建图搞的。然后参照了别人的博客。这个解法比较好
利用在SPFA维护入队次数。入队次数大于节点数目的位于负环。
那么负环中的点如何DFS到终点。（SPFA从起点开始如果能找到入队大于N那么一定可以从起点到这个点）那么就NOBOUND；
VOID和输出ANS就比较容易了
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == ? b : gcd(b, a % b);}
#define MAXN 2000
#define MAXM 20010
const int INF = 0x3f3f3f3f;
int N,M,A,B;
struct node
{
int u,v,next;
int length,weight;
}edge[MAXM];
int head[MAXN],cnt;
int num[MAXN],d[MAXN],l[MAXN];
bool inq[MAXN],used[MAXN];
int q[MAXM];
bool found;
void insert(int u ,int v,int weight,int length)
{
if (head[u] != - && weight > edge[head[u]].weight) return;
if (head[u] != - && weight < edge[head[u]].weight) head[u] = -;
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].weight = weight;
edge[cnt].length = length;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void read()
{
memset(head,-,sizeof(head));
cnt = ;
for (int i = ; i < M; i++)
{
int u ,v, weightl,weightr,length;
// if (i != M - 1)
scanf("(%d,%d,%d[%d]%d) ",&u,&v,&weightl,&length,&weightr);
// else scanf("(%d,%d,%d[%d]%d)",&u,&v,&weightl,&length,&weightr);
//printf("%d %d %d %d %d \n",u,v,weightl,length,weightr);
insert(u,v,weightl,length);
insert(v,u,weightr,length);
}
}
bool SPFA(int s)
{
int front = ,rear = ;
memset(inq,false,sizeof(inq));
memset(num,,sizeof(num));
memset(d,0x3f,sizeof(d));
memset(l,0x3f,sizeof(l));
inq[s] = true;
q[] = s;
d[s] = l[s] = ;
num[s] = ;
while (front !=rear)
{
int u = q[front] ;
front = (front + ) % MAXM;
inq[u] = false;
for (int i = head[u]; i != - ; i = edge[i].next)
{
int v = edge[i].v;
if (d[v] > d[u] + edge[i].weight ||( (d[v] == d[u] + edge[i].weight) && (l[v] > l[u] + edge[i].length)))
{
d[v] = d[u] + edge[i].weight;
l[v] = l[u] + edge[i].length;
if (!inq[v])
{
inq[v] = true;
num[v]++;
q[rear] = v;
rear = (rear + ) % MAXM;
if (num[v] > N + ) return false;
}
}
}
}
return true;
}
void dfs(int cur)
{
used[cur] = true;
if (cur == B) {found = true; return;}
for (int i = head[cur]; i != -; i = edge[i].next)
{
int v = edge[i].v;
if (!used[v]) dfs(v);
}
}
int main()
{
// freopen("sample.txt","r",stdin);
while (scanf("%d%d%d%d ",&N,&M,&A,&B) != EOF)
{
found = false;
read();
bool flag = SPFA(A);
if (d[B] == INF) puts("VOID");
else
{
if (flag) printf("%d %d\n",d[B],l[B]);
else
{
for (int i = ; i < N; i++)
if (num[i] > N)
{
memset(used,false,sizeof(used));
found = false;
dfs(i);
if (found) break;
}
if (found || num[B] > N) puts("UNBOUND");
else printf("%d %d\n",d[B],l[B]);
}
}
}
return ;
}