A38154. 最短路给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.输入第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所…
填空题
困难
知识点
题目描述
最短路
给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.
输入
第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.
输出
对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.
样例输入
4
5 7 1
1 2 3
2 3 4
3 4 8
1 3 9
4 5 1
1 4 5
1 5 10
4 4 1
1 2 -4
2 3 8
1 3 5
3 4 0
3 3 2
1 2 -3
2 3 -4
3 1 6
4 2 1
1 2 1
3 4 2
样例输出
0 3 7 5 6
0 -4 4 4
Error
0 1 null null
参考答案
#include<iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <functional>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <algorithm>
#define ll long long
#define PI acos(-1)
#define mes(x,y) memset(x,y,sizeof(x))
#define lp pair<ll, ll>
#define FAST_IO ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0)
using namespace std;
const ll inf = 60000;
const ll mod = 1e9;
ll n, m, i, j, k = 0, t, w, flag, x, y, z, sum;
string s1, s2, s;
ll head[30010],dis[30010],step[30010],ismove[30010];
struct node {
ll end, len, next;
}
p[30010];
void add(ll st, ll en, ll len) {
p[++sum].end = en;
p[sum].len = len;
p[sum].next = head[st];
head[st] = sum;
}
bool Spfa(ll st) {
mes(dis, inf);
mes(ismove, 0);
mes(step, 0);
stack<ll>que;
que.push(st);
dis[st] = 0;
while (!que.empty()) {
ll v = que.top();
que.pop();
ismove[v] = 0;
for (ll i = head[v]; i; i = p[i].next) {
w = p[i].end;
if (dis[w] > dis[v] + p[i].len) {
dis[w] = dis[v] + p[i].len;
if (!ismove[w])que.push(w);
ismove[w] = 1;
step[w]++;
if (step[w] > n)return false;
}
}
}
return true;
}
int main() {
while (cin >> k) {
while (k--) {
cin >> n >> m >> t;
for (i = sum = 0, mes(head, 0); i < m; i++) {
cin >> x >> y >> z;
add(x, y, z);
}
if (Spfa(t)) {
for (i = 1; i <= n; i++) {
if (dis[i] == dis[n+1]) cout << "null"; else cout << dis[i];
if (i < n)cout << " ";
}
} else {
cout << "Error";
}
cout << endl;
}
}
return 0;
}
上一题
下一题