游客 注册 | 登录
中文 | En

3706 - 带负权的单源最短路

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

 输入一个有向网络图，边的权值可正可负，求顶点到其他各点的最短路。

题目输入

第一行输入n，表示n个结点（默认顶点为0号）

接下来输入n*n矩阵。表示各边的权值。

题目输出

输出一行，如果有负权回路输出“not possible”，否则输出顶点0到其他点的最短路，输出答案之间仅有一个空格，结尾没有空格。

输入/输出样例

输入格式

4
0 0 -3 0
2 0 0 0
0 -1 0 -4
0 0 0 0

输出格式

not possible

C++解答

#include <iostream>
#include <algorithm>
#include <queue>
#define SIZE 1000
#define INF 1000000000

using namespace std;

int n;
int matrix[SIZE][SIZE];
int dis[SIZE], nums[SIZE];
bool inq[SIZE];

bool SPFA(int s) {
	fill(nums, nums + n, 0);
	fill(dis, dis + n, INF);
	fill(inq, inq + n, false);
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	nums[s]++;
	inq[s] = true;
	int p;
	while (!q.empty()) {
		p = q.front();
		q.pop();
		inq[p] = false;
		for (int j = 0; j < n; j++) {
			if (matrix[p][j] != 0) {
				if (dis[p] + matrix[p][j] < dis[j]) {
					dis[j] = dis[p] + matrix[p][j];
					if (false == inq[j]) {
						q.push(j);
						inq[j] = true;
						nums[j]++;
						if (nums[j] >= n) return false;
					}
				}
			}
		}
	}
	return true;
}

int main() {
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++)
		    for (int j = 0; j < n; j++)
		        scanf("%d", &matrix[i][j]);
		if (SPFA(0)) {
			for (int i = 1; i < n; i++) {
				printf("%d", dis[i]);
				if (i != n - 1) printf(" ");
			}
		} else printf("not possible");
		printf("\n");
	}
	return 0;
}
请先登陆