| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求大神指导如何WA了??半天没看出来哪里错误。。测试都过#include <stdio.h>
#include <string.h>
#define MAX_NUMBER 300000
#define MAX_POINT 20000
#define INF 1000000000
struct Edge {
int start_point;
int end_point;
int distance;
};
struct Edge edge[MAX_NUMBER];
int distance[MAX_POINT];
int edge_number, point_number;
int bellmanFord() {
int i, k, flag;
int start_point, end_point;
for (i = 1; i < point_number + 1; i++) {
distance[i] = INF;
}
distance[1] = 0;
for (i = 1; i < point_number; i++) {
flag = 0;
for (k = 0; k < edge_number; k++) {
start_point = edge[k].start_point;
end_point = edge[k].end_point;
if (distance[start_point] != INF && distance[end_point] > distance[start_point] + edge[k].distance) {
distance[end_point] = distance[start_point] + edge[k].distance;
flag = 1;
}
}
if (!flag) {
break;
}
}
for (i = 0; i < edge_number; i++) {
start_point = edge[i].start_point;
end_point = edge[i].end_point;
if (distance[end_point] > distance[start_point] + edge[i].distance) {
return 0;
}
}
return 1;
}
int main() {
int ML, MD, start_point, end_point, two_distance;
int i;
while (scanf("%d%d%d", &point_number, &ML, &MD) != EOF) {
edge_number = 0;
for (i = 0; i < ML; i++) {
scanf("%d%d%d", &start_point, &end_point, &two_distance);
edge[edge_number].start_point = start_point;
edge[edge_number].end_point = end_point;
edge[edge_number].distance = two_distance;
edge_number++;
}
for (i = 0; i < MD; i++) {
scanf("%d%d%d", &start_point, &end_point, &two_distance);
edge[edge_number].start_point = end_point;
edge[edge_number].end_point = start_point;
edge[edge_number].distance = -two_distance;
edge_number++;
}
if (!bellmanFord()) {
printf("-1\n");
}
else {
if (distance[point_number] == INF) {
printf("-2\n");
}
else {
printf("%d\n", distance[point_number]);
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator