白駿アルゴリズム13424号:秘密会議

リンク

https://www.acmicpc.net/problem/13424

質問する

ハリーと友人たちは、ムブリッジの監視を避けるために、暗い魔法防御術を練習するための秘密のパーティーを開くつもりだ.彼らは偽のガレオンを使ってパーティーの場所を伝えているが、誰も知らない.ハリーが自分の偽のガレオンにパーティーの場所を書いたら、友达が持っている偽のガレオンにハリーの少ない場所が現れる.ハリーが通っているホグワット魔法学校には、パーティーで使えるN部屋がある.各部屋には1からNの番号が付いていて、重複した番号はありません.魔法学校のように、N部屋はM魔法でできた秘密の通路でつながっている.すべての秘密通路は双方向に通行でき、自然水の長さを持っている.パーティーに参加した友達はK人です.
ハリーはN部屋の中から今日のパーティーの場所を選ぶつもりだ.パーティーの場所を決める前に、ホグワートの秘密地図で学校の人の現在の位置を確認したところ、パーティーに参加した友达がそれぞれN部屋の1部屋にいることが分かった.残念なことに、ホグワーツは瞬間移動を禁止し、パーティーに参加した友人たちが発見されないように、秘密の通路を利用して今日のパーティー場所に行きたいだけだ.この場合、彼らはいつも最初の位置からパーティーの場所までの移動距離が最も短い経路しか使用しません.ここで、「移動距離」とは、最初の位置から会合場所まで使用される秘密通路の長さの和を意味する.どの部屋をパーティーの場所として使うかを考えていたハリーは、パーティーに参加した友达の移動距離の合計が最も小さい部屋を今日のパーティーの場所として使うことにした.下図は、N=6、M=7、K=2の例である.

上図の各頂点の数字は部屋の番号で、幹線の数字は部屋と部屋を結ぶ秘密の通路の長さです.パーティーに参加した2人の友達は今3号室、5号室にいます.2号室を今日のパーティーの場所として使えば、3号室の友人Aの最短経路は3号室-2号室で、移動距離は2です.5号室の友人Bの場合、2号室に行く最短経路は5号室-1号室-3号室-2号室で、移動距離は5です.このとき,2人の友人の移動距離の合計は7である.しかし,1号室を会合場所として選択すると,友人Aの移動距離は1,友人Bの移動距離は2,友人2人の移動距離の合計は3となる.上記の例では、1号室、3号室、または5号室を今日のパーティーの場所として使用した場合、友人の移動距離の合計は最小3となります.
ハリーが今日のパーティーの場所を偽ガレオンに書いたら、パーティーに参加したK人の友達はすぐにそれを知って、今のすべての仕事を中断して、すぐに今日のパーティーの場所に行きます.ハリーのためにプログラムを作成し、パーティーの場所を見つけて印刷し、友达の移動距離の合計を最小限に抑える.

入力

入力データは標準入力を採用している.入力はT個のテストデータからなる.入力された第1行は、試験用例の個数を表す自然数Tを与える.各試験例の第1行において、部屋の個数N(2≦N≦100)、秘密チャネルの個数M(N−1≦M≦N(N−1)/2)が空白に分割された.次の行から、秘密チャネルの情報(a,b,c)がM行に与えられる.aとbは暗号チャネルを介して接続された2つの部屋の番号であり、cはaとbを接続する暗号チャネルの長さである.aとbは常に異なり,cは1以上1000以下の自然数である.2つの部屋を結ぶ秘密の通路は1つしか存在しない必要があります.また,一つの部屋から別の部屋へ秘密通路が使用できない場合もなく,同じ秘密通路についての重複情報も存在しない.すべての秘密チャネルの情報を与え、次の行でパーティーに参加する友人の数K(1≦K≦N)を与える.各テストケースの最後の行には,パーティーに参加した友人たちが現在いる部屋の番号Kが空白であることが示されている.友人がいる部屋はいつもN部屋のうちの1つで、部屋番号を繰り返すことはありません.つまり、2人以上が1つの部屋にいると入力されません.

しゅつりょく

出力は標準出力を採用する.入力したデータについて、各テスト例の答えを順番に1行ずつ出力します.各テストケースでは、パーティーに参加する友人の移動距離の合計を最小限に抑えるために、パーティーの場所の部屋番号が印刷されます.そのような場所が複数ある場合は、その中で最も番号の小さい部屋の番号を出力します.

入力と出力の例

プールコード（C++）

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tiii = tuple<int,int,int>;

const int INF = int(1e9) + 7;
int n,m,k;

int dist[101][101];

void reset(){
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= n; j++){
      dist[i][j] = i==j ? 0 : INF;
    }
  }
}

void floyd(){
  for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
}

int main(){
  fastio;
  int tc; cin >> tc;
  while(tc--){
    cin >> n >> m;
    reset();
    for(int i = 0; i < m; i++){
      int a,b,c; cin >> a >> b >> c;
      dist[a][b] = min(dist[a][b], c);
      dist[b][a] = min(dist[b][a], c);
    }
    cin >> k;
    vi v(k);
    for(int i = 0; i < k; i++) cin >> v[i];
    floyd();
    int ans = INF,c = 0;
    for(int i = 1; i <= n; i++){
      int cnt = 0;
      for(int j = 0; j < v.size(); j++){
        cnt += dist[v[j]][i];
      }
      if(ans > cnt){
        ans = cnt;
        c = i;
      }
    }
    cout << c << "\n";
  }
  return 0;
}

nこれ...100歳だったのでフロイド・ワッシャーを使いました.
友達がいる位置からすべての頂点までの距離を全部合わせて、最小値の位置を印刷すればいいです.