C0ns1st @ 2024-09-13 20:20:56
这题我一看是个黄，啪一下点进来了。
然后思考了很长时间，没头绪，点进题解一看...
好家伙，至少50行.
虽然我知道这是个板子题，但是涉及的知识肯定不止普及，所以放到普及+/提高是很合理的。
顺便，本人是蒟蒻，准备考csp-j，所以有不理智的发言请见谅，不喜勿喷QAQ
by C0ns1st @ 2024-09-15 09:01:03
主要是，这个题和P5788是一个量级的模板题？？？
所以我才搞了这个帖子
by ATION001 @ 2024-11-10 15:55:22
建一个正边和一个反边然后分别跑一边 Dijkstra 不就好了？
by K_func @ 2024-12-30 21:12:19
@C0ns1st Bellman-ford：我不存在了
by K_func @ 2024-12-30 21:13:29
@C0ns1st Bellman-ford37行
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<tuple<int,int,int>> l;
vector<tuple<int,int,int>> r;
long long bellman_ford(vector<tuple<int,int,int>>& lists){
vector<long long> dst(1000005,4e18);
int s=1;
dst[1]=0;
for(int i=1;i<n;i++){
bool changed=0;
for(auto x : lists){
auto [u,v,w]=x;
if(dst[u]+w<dst[v]){
dst[v]=dst[u]+w;
changed=1;
}
}
if(!changed) break;
}
long long ans=0;
for(int i=1;i<=n;i++){
ans+=dst[i];
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
l.push_back({u,v,w});
r.push_back({v,u,w});
}
cout<<bellman_ford(l)+bellman_ford(r);
return 0;
}