好好的gdy你不问非要来问谷民
by lelml @ 2022-08-21 10:04:24
gdy你不问非要来问谷民
by Fast_IO @ 2022-08-21 10:06:03
```cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 100005;
struct node{
int v,c,nxt;
}e[MAXN << 1];
int tot = 0, head[MAXN], n, m;
void addEdge(int u, int v, int c){
e[++tot].v = v;
e[tot].c = c;
e[tot].nxt = head[u];
head[u] = tot;
}
int s = 0, dis[MAXN], vis[MAXN], num[MAXN];
queue <int> q;
bool spfa(){
memset(dis, ~0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
q.push(s);
num[s] = 1;
vis[s] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if(dis[v] < dis[u] + e[i].c) {
dis[v] = dis[u] + e[i].c;
if(!vis[v]) {
q.push(v);
vis[v] = 1;
num[v]++;
if(num[v] > n + 3) return false;
}
}
}
}
return true;
}
int main(){
int n,m;
cin >> n >> m;
while(m--){
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, -w);
}
for(int i = 1; i <= n; i++) addEdge(0, i, 0);
if(!spfa()) cout << "NO SOLUTION";
else for(int i = 1; i <= n; i++) cout << dis[i] << endl;
return 0;
}
```
现在55
by tzl_Dedicatus545 @ 2022-08-21 10:07:24