답안 #671927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671927 2022-12-14T09:32:53 Z Kenpar Alias (COCI21_alias) C++17
70 / 70
93 ms 620 KB
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl '\n'
 
const ll MOD = 1e9+7;
const ll INF = 1e18;
const ll MAX = 2500;

void solve(){
	map<string,int> toInt;
	set<string> used;
	int n,m;
	cin>>n>>m;

	int cur = 0;
	vector<vector<pair<ll,ll>>> edges(n);
	for(int i = 0; i < m; i++){
		string a,b; ll c;
		cin>>a>>b>>c;

		int aInd, bInd;
		if(!used.count(a)){
			aInd = cur;
			toInt[a] = cur;
			cur++;
			used.insert(a);
		}else{
			aInd = toInt[a];
		}

		if(!used.count(b)){
			bInd = cur;
			toInt[b] = cur;
			cur++;
			used.insert(b);
		}else{
			bInd = toInt[b];
		}

		edges[aInd].push_back({bInd, c});
	}

	int q;
	cin>>q;

	for(int i = 0; i < q; i++){
		vector<ll> dist(n, INF);

		string aTemp, bTemp; cin>>aTemp>>bTemp;
		int a = toInt[aTemp], b = toInt[bTemp];

		priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;

		pq.push({0,a});

		while(!pq.empty()){
			pair<ll,ll> top = pq.top();
			pq.pop();

			if(dist[top.second] <= top.first) continue;

			dist[top.second] = top.first;

			for(pair<ll,ll> edge : edges[top.second]){
				pq.push({top.first + edge.second, edge.first});
			}
		}

		if(dist[b] == INF) cout<<"Roger";
		else cout<<dist[b];

		cout<<endl;
	}
}

int main() 
{
    cin.tie(NULL);
    ios::sync_with_stdio(NULL);
    int t = 1;
    //cin>>t;

    int temp = t;
    while(t--){
        //cout<<"Case #"<<temp - t<<" > "<<endl;
        solve();
 
        cout<<endl;
    }

}

Compilation message

alias.cpp: In function 'int main()':
alias.cpp:85:9: warning: unused variable 'temp' [-Wunused-variable]
   85 |     int temp = t;
      |         ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 93 ms 456 KB Output is correct
4 Correct 83 ms 476 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct