D- People on a Line
コンテスト中に解けなくて悲しい思いをした問題。
コンテスト中に考えてたこと
・全点対最短路を求めることができたら良さそう。
・有効辺のみなので、dfs(コンテスト中はDijkstraをした)時にusedとdを持つと解ける。
(つまりdfsごとに到達と距離の配列を持つ必要がある)
・グラフは非連結の場合がある。↑の方針だとグラフの数だけ配列が必要になって解けそうにない。
正解のときに考えたこと
・1つの座標を決めることで、全ての座標が決まる。
・逆辺を貼ることで、一度のdfsで到達したか、どうかを判定する配列を持つ必要がない。
・これトポロジカル順にソートすると逆辺はらなくてよくない?
・訪問した頂点の全ての辺について探索を行うので、再訪問の必要はない(よって間に合う。
トポロジカルソートでもうまいことやると解けるらしい。
#include<bits/stdc++.h> using ll = long long; #define int ll #define INF 100000000000000LL #define rep(i,n) for(int i=0;i<n;i++) using namespace std; using pii = pair<int,int>; vector<bool>used; vector<vector<pii>>edge; vector<int>d; bool judge=true; void dfs(int v,int val){ used[v]=true; rep(i,edge[v].size()){ int next=edge[v][i].first; int cost=edge[v][i].second; if(d[next]==INF){ d[next]=val+cost; if(!used[next])dfs(next,d[next]); }else if(d[next]!=cost+val){ judge=false; } } } signed main(){ int n,m; cin>>n>>m; edge = vector<vector<pii>>(n); used = vector<bool>(n,false); d = vector<int>(n,INF); rep(i,m){ int a,b,c;cin>>a>>b>>c; --a,--b; edge[a].push_back(make_pair(b,c)); edge[b].push_back(make_pair(a,-c)); } rep(i,n)if(!used[i])dfs(i,0); cout << (judge ? "Yes" : "No") << endl; }
2019/6月追記
コードがひどすぎたので直した。