Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<map>
- #include<vector>
- #include<cstdio>
- #include<string>
- #include<queue>
- using namespace std;
- const int INF = 1 << 30;
- const int MAX = (int)1e5 + 1;
- map< string, int > M;
- map< string, int > :: iterator it;
- vector < pair < int , int > > graph[MAX];
- int dist[ MAX ];
- int used[ MAX ];
- int main() {
- char name[20];
- int T;
- scanf("%d",&T);
- for(int t = 0; t < T; ++t) {
- int N;
- scanf("%d",&N);
- for(int i = 1; i <= N; ++i) {
- int cityCount;
- scanf("%s%d",name,&cityCount);
- M.insert( pair < string, int >(name,i));
- for(int j = 1; j <= cityCount; ++j) {
- int to;
- int weight;
- scanf("%d%d",&to,&weight);
- graph[i].push_back( pair< int, int >(weight,to));
- }
- }
- int q;
- scanf("%d",&q);
- for(int j = 0; j < q; ++j) {
- scanf("%s",name);
- it = M.find(name);
- int from = (*it).second;
- scanf("%s",name);
- it = M.find(name);
- int to = (*it).second;
- priority_queue< pair < int, int >, vector< pair < int, int > >, greater < pair < int, int > > > PQ;
- PQ.push( pair < int, int >(0,from) );
- for(int i = 1; i <= N; ++i ) {
- dist[i] = INF;
- used[i] = 0;
- }
- dist[from] = 0;
- while(!PQ.empty()) {
- int v = PQ.top().second;
- int w = PQ.top().first;
- PQ.pop();
- if(used[v]) continue;
- int currentSize = graph[v].size();
- for(int m = 0; m < currentSize; ++m) {
- int toV = graph[v][m].second;
- int toW = graph[v][m].first;
- if(!used[toV] && dist[v] + toW < dist[toV]) {
- dist[toV] = dist[v] + toW;
- PQ.push( pair < int, int >(dist[toV],toV));
- }
- }
- used[v] = 1;
- if(v == to) break;
- }
- printf("%d\n",dist[to]);
- }
- for(int i = 1; i <= N; ++i) graph[i].clear();
- M.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement