11792 - Krochanska is Here!
問題概要
複数の路線が与えられ、ある駅が複数の路線に含まれるような駅を"important station"という。各important stationについて、他のimportant stationへ行く最短時間の平均が最小になるようなimportant stationを求めよう。ただし、それが複数ある場合は、IDの小さいものとする。
コード
#include<iostream> #include<vector> #include<queue> #include<set> #include<algorithm> #define INF (1<<22) using namespace std; struct node{ int w; int cnt; vector<int> vcon; node():w(INF),cnt(0){} }; typedef vector<node> graph; void BFS( graph &G, int st ){ queue<int> q; bool visited[G.size()+1]; fill(visited,visited+G.size()+1,false); visited[st]=true; q.push( st ); while( !q.empty() ){ int now = q.front(); q.pop(); for(unsigned int i = 0; i < G[ now ].vcon.size(); ++i){ int next = G[ now ].vcon[i]; if( !visited[ next ] ){ visited[ next ] = true; q.push( next ); G[ next ].w = G[ now ].w + 2; } } } } int main(){ int T; cin >> T; for(int tc=1; tc<=T; ++tc){ int ans; int minsum = INF; graph G; int N,S; cin >> N >> S; int cnt[N+1]; fill(cnt,cnt+N+1,0); G.resize(N+1); for(int i = 0; i < S; ++i){ int src; cin >> src; cnt[src]++; while(true){ int dst; cin >> dst; if( dst == 0 ) break; G[src].vcon.push_back(dst); G[dst].vcon.push_back(src); src = dst; cnt[dst]++; } } for(unsigned int i = 1; i < G.size(); ++i){ if( cnt[i] > 1 ){ int sum = 0; G[i].w = 0; BFS( G, i ); for(unsigned int j = 1; j < G.size(); ++j){ if( cnt[j] > 1 ){ sum += G[j].w; } } if( sum < minsum ){ minsum = sum; ans = i; }else if(sum == minsum && i < ans ){ ans = i; } } } cout << "Krochanska is in: " << ans << endl; } return 0; }
解法
コストが固定だから、各important stationを始点にBFSする。計算量は100*10000くらいだと思うが、なんとか間に合う。