codeforces 368 div2 B. Bakery

問題

問題概要

小麦屋さん以外の頂点でパン屋を開こうとする場合に、もっとも小麦屋さんから近くでパン屋を開ける頂点までの距離をもとめよ。開けないなら-1。

解法

ダイクストラで解いた。スタートをすべての小麦屋さんにして、それらの頂点からほかの頂点までの最短距離を求めた。さいごに、小麦屋さん以外の頂点で距離が最小のもとを答えとすればいい。
ほかの人の回答をみていたら、ダイクストラで書いている人はいなくて、小麦屋さんに隣接する小麦屋でない頂点までの距離の中で最短のものを答えとしている回答が多かった。パン屋を開けるなら確実に1つの頂点は小麦屋と隣接しているはずなので、こういう回答でいいよね。

ミス

完全にめんどくさいことしていた。

コード

ダイクストラ解法

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
const ll INF = 1e12;

int n, m, k;
vector<pair<int, int> > G[100010];
ll dist[100010];
int main(void){
    cin >> n >> m >> k;
    rep(i, m){
        int u, v, l; cin >> u >> v >> l;
        u--; v--;
        G[u].push_back(make_pair(v, l));
        G[v].push_back(make_pair(u, l));
    }
    vector<int> a;
    set<int> strage;
    rep(i, k){
        int tm; cin >> tm;
        tm--;
        a.push_back(tm);
        strage.insert(tm);
    }
    
    rep(i, 100010) dist[i] = INF;
    priority_queue<P, vector<P>, greater<P> > q;
    rep(i, k){
        q.push(make_pair(0, a[i]));//strage is start
        dist[a[i]] = 0;
    }

    while(!q.empty()){
        ll d = q.top().first;
        int u = q.top().second;
        q.pop();
        if(d > dist[u]) continue;
        for(auto tm : G[u]){
            int v = tm.first;
            ll len = tm.second;
            if(d + len < dist[v]){
                dist[v] = d + len;
                q.push(make_pair(dist[v], v));
            }
        }
    }

    ll ans = INF;
    rep(i, n){
        if(strage.count(i) == 0){
            ans = min(ans, dist[i]);
        }
    }

    if(ans != INF)printf("%d\n", ans);
    else printf("-1\n");
    return 0;
}

strageに隣接する頂点をみる解法

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
const ll INF = 1e12;

int n, m, k;
vector<pair<int, int> > G[100010];
ll dist[100010];
int main(void){
    cin >> n >> m >> k;
    rep(i, m){
        int u, v, l; cin >> u >> v >> l;
        u--; v--;
        G[u].push_back(make_pair(v, l));
        G[v].push_back(make_pair(u, l));
    }
    vector<int> a;
    set<int> strage;
    rep(i, k){
        int tm; cin >> tm;
        tm--;
        a.push_back(tm);
        strage.insert(tm);
    }
        
    ll ans = INF;
    rep(i, a.size()){// u is starage
        int u = a[i];
        for(auto t : G[u]){
            int v = t.first;
            ll len = t.second;
            if(strage.count(v) == 0){// v is not strage
                ans = min(ans, len);
            }
        }
    }

    if(ans != INF)printf("%d\n", ans);
    else printf("-1\n");
    return 0;
}