予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

D- People on a Line

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月追記
コードがひどすぎたので直した。