AC代码与思路
反向建边，然后注意bfs的逻辑一定要清楚，要以什么为当前点，什么为父节点，不要混淆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+10;
ll n,m,ans[MAXN];
bool vis[MAXN];
struct edge {
ll u,v,w;
};
vector<edge> e[MAXN];
edge make_edge(ll u,ll v,ll w) {
edge a;a.u=u;a.v=v;a.w=w;
return a;
}
deque <edge> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) {
ll ui,vi,wi;
cin>>ui>>vi>>wi;
e[ui].push_back(make_edge(ui,vi,wi));
e[vi].push_back(make_edge(vi,ui,-wi));
}
for(int i=1;i<=n;i++) {
if(vis[i])
continue;
q.clear();
q.push_back(make_edge(0,i,0));
while (!q.empty()) {
ll ui=q.front().u,vi=q.front().v,wi=q.front().w;
q.pop_front();
if(vis[vi])
continue;
for(int j=0;j<e[vi].size();j++) {
if(!vis[e[vi][j].v])
q.push_back(make_edge(e[vi][j].u,e[vi][j].v,e[vi][j].w));
}
vis[vi]=true;
ans[vi]=ans[ui]+wi;
}
}
for(int i=1;i<=n;i++) {
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
|
心路历程
这个代码稍微有点搞笑，样例都没过
https://atcoder.jp/contests/abc373/submissions/58559275
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+10;
ll n,m,ans[MAXN];
struct edge {
ll u,v,w;
};
vector<edge> e[MAXN];
edge make_edge(ll u,ll v,ll w) {
edge a;a.u=u;a.v=v;a.w=w;
return a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) {
ll ui,vi,wi;
cin>>ui>>vi>>wi;
e[ui].push_back(make_edge(ui,vi,wi));
}
for(int i=1;i<=n;i++) {
while (!e[i].empty()) {
ll ui=e[i].back().u,vi=e[i].back().v,wi=e[i].back().w;
e[i].pop_back();
ans[vi]=ans[ui]+wi;
}
}
for(int i=1;i<=n;i++) {
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
|
我仔细想了一下这个问题，发现如果不知道次序就很难解，于是我仔细开始想拓扑排序的可能性。
想不到确实不是。
这句第一个条件其实是没有重复路，二条件是规定有向图，没提到过无环
而且就算知道次序也会坐牢
可以走反边5→2→1→3→6(其中 2→1 以及 3→6 是反边)