2 条题解
-
2许栋轶 LV 10 @ 2022-11-6 16:41:12
#include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; LL head[N], to[N], w[N], idx, ne[N]; LL dis[N], vis[N], num[N]; inline void add(int x, int y , int z) { to[++idx] = y; w[idx] = z; ne[idx] = head[x]; head[x] = idx; } LL n, m, s; bool spfa(int k) { memset(num , 0, sizeof(num)); memset(vis , 0, sizeof(vis)); memset(dis , 0x3f, sizeof(dis)); stack<int> p;//先进后出 //可能会有负环点进队列时,马上就出队列了 //所以用栈 p.push(k); vis[k] = 1; dis[k] = 0; num[k]++; while(!p.empty()) { int t = p.top(); p.pop(); vis[t] = 0; for(int i = head[t]; i ; i = ne[i]) { if(dis[to[i]] > w[i] + dis[t]) { dis[to[i]] = w[i] + dis[t]; if(!vis[to[i]]) { p.push(to[i]); num[to[i]]++; vis[to[i]] = 1; if(num[to[i]] >= n) return true; } } } } return false; } int main() { scanf("%lld%lld%lld", &n, &m, &s); for(LL i = 0, x, z, y; i < m; i++) { scanf("%lld%lld%lld", &x, &y, &z); add(x, y, z); } //超级原点 int k = n + 1; for(int i = 1; i <= n; i++) add(k, i, 0); //如果1 2 3联通,而4 5是负环,先判断有无负环 if(spfa(k)) { //有,输出-1 cout << "-1" << endl; } //没有,进行运算 else { spfa(s); for(int i = 1; i <= n; i++) { if(dis[i] >= INF) { puts("NoPath"); //不联通 } else { printf("%lld\n",dis[i]); //输出值 } } } return 0; }
-
12021-11-13 17:13:04@
/***************************************** 备注: ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; LL head[N] , to[N] , w[N] , idx,ne[N]; LL dis[N] , vis[N], num[N] ,st[N] ,top = 0; inline void add(int x, int y , int z) { to[++idx] = y; w[idx] = z; ne[idx] = head[x]; head[x] = idx; } LL n , m , s; bool spfa(int k) { memset(num , 0 ,sizeof(num)); memset(vis , 0 ,sizeof(vis)); memset(dis , 0x3f ,sizeof(dis)); st[++top] = k; vis[k] = 1; dis[k] = 0; num[k]++; while(top > 0) { int t = st[top--]; vis[t] = 0; for(int i = head[t] ; i ; i = ne[i]) { if(dis[to[i]] > w[i] + dis[t]) { dis[to[i]] = w[i] + dis[t]; if(!vis[to[i]]) { st[++top] = to[i]; num[to[i]]++; vis[to[i]] = 1; if(num[to[i]] >= n) return true; } } } } return false; } int main() { scanf("%lld%lld%lld",&n,&m,&s); for(LL i =0,x,z,y ; i < m ; i++) { scanf("%lld%lld%lld",&x,&y,&z); add(x,y,z); } int k = n+1; for(int i = 1; i <= n ; i++) add(k , i , 0); if(spfa(k)) cout << -1; else { spfa(s); for(int i = 1 ; i <= n ; i++) { if(dis[i] >= INF) puts("NoPath"); else printf("%lld\n",dis[i]); } } return 0; }
- 1
信息
- ID
- 420
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 8
- 标签
- 递交数
- 306
- 已通过
- 55
- 上传者