NC50386. Easy SSSP
描述
输入描述
第一行三个正整数，分别为点数N，边数M，源点S；
以下M行，每行三个整数a,b,c，表示点a,b之间连有一条边，权值为c。
输出描述
如果存在负权环，只输出一行-1，否则按以下格式输出：
共N行，第i行描述S点到点i的最短路：
如果S与i不连通，输出NoPath；
如果i=S，输出0。
其他情况输出S到i的最短路的长度。
示例1
输入:
6 8 1 1 3 4 1 2 6 3 4 -7 6 4 2 2 4 5 3 6 3 4 5 1 3 5 4
输出:
0 6 4 -3 -2 7
C++14(g++5.4) 解法, 执行用时: 654ms, 内存消耗: 1560K, 提交时间: 2020-01-01 21:17:48
#include<bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w;
};
int main() {
int N, M, S;
cin >> N >> M >> S;
vector<Edge> edges(M);
for (auto &e: edges) cin >> e.u >> e.v >> e.w;
vector<long long> dis(N + 1, 0x3f3f3f3f3f3f3f3f);
dis[S] = 0;
for (int i = 0; i < N; i++) {
bool ok = false;
for (auto e: edges) {
// if (dis[e.u] == 0) continue;
if (dis[e.v] > dis[e.u] + e.w) {
ok = true;
dis[e.v] = dis[e.u] + e.w;
}
}
if (!ok) break;
if (i == N - 1) {
cout << -1 << endl;
return 0;
}
}
for (int i = 1; i <= N; i++) {
if (dis[i] > 0x1f1f1f1f1f1f1f1f) cout << "NoPath" << endl;
else cout << dis[i] << endl;
}
}
C++11(clang++ 3.9) 解法, 执行用时: 556ms, 内存消耗: 1636K, 提交时间: 2020-05-28 10:04:32
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
int u,v,w;
};
int main()
{
int N,M,S;
cin>>N>>M>>S;
vector<Edge> edges(M);
for(auto &e:edges)
cin>>e.u>>e.v>>e.w;
vector<long long> dis(N+1,0x3f3f3f3f3f3f3f3f);
dis[S]=0;
for(int i=0;i<N;i++)
{
bool ok=false;
for(auto e:edges)
{
if(dis[e.v]>dis[e.u]+e.w)
{
ok=true;
dis[e.v]=dis[e.u]+e.w;
}
}
if(!ok) break;
if(i==N-1)
{
cout<<-1<<endl;
return 0;
}
}
for(int i=1;i<=N;i++)
{
if(dis[i]>0x1f1f1f1f1f1f1f1f) cout<<"NoPath"<<endl;
else cout<<dis[i]<<endl;
}
}