3706 - 带负权的单源最短路
输入一个有向网络图，边的权值可正可负，求顶点到其他各点的最短路。
Input
第一行输入n，表示n个结点（默认顶点为0号）
接下来输入n*n矩阵。表示各边的权值。
Output
输出一行，如果有负权回路输出“not possible”，否则输出顶点0到其他点的最短路，输出答案之间仅有一个空格，结尾没有空格。
Examples
Input
4 0 0 -3 0 2 0 0 0 0 -1 0 -4 0 0 0 0
Output
not possible
Solution 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; }