oj.uz

답안 #812299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
812299 2023-08-07T08:16:06 Z Tunglam07 Alias (COCI21_alias) C++17
70 / 70
 38 ms 468 KB 
#include<bits/stdc++.h>
using namespace std;
 
map<string, int> mp;
vector<pair<int, int> > vec[1001];
long long dp[1001], cnt, n, m, q;
 
int ckstr(string x)
{
	if (mp.find(x) == mp.end())	
	{
		mp[x] = cnt++;
	}
	return mp[x];
}

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) 
	{
		int t;
		string x, y;
		cin >> x >> y >> t;
		vec[ckstr(x)].push_back(pair<int, int>(ckstr(y), t));
	}
	cin >> q;
	while(q--)
	{
		string x, y;
		cin >> x >> y;
		set<pair<long long, int> > s;
		memset(dp, -1, sizeof dp);
		dp[ckstr(x)] = 0;
		s.insert(pair<long long, int>(0, ckstr(x)));
		while (!s.empty())
		{
			pair<long long, int> id = *s.begin();
			s.erase(id);
			int ckid = id.second;
			for (int j = 0; j < (int)vec[ckid].size(); j++) 
			{
				int nxt = vec[ckid][j].first;
				int d = vec[ckid][j].second;
				if (dp[nxt] == -1 || dp[nxt] > dp[ckid] + d) 
				{
					s.erase(pair<long long, int>(dp[nxt], nxt));
					dp[nxt] = dp[ckid] + d;
					s.insert(pair<long long, int>(dp[nxt], nxt));
				}
			}
		}
		if (dp[ckstr(y)] == -1)
		{
			cout << "Roger" << endl;
		}
		else	
		{
			cout << dp[ckstr(y)] << endl;
		}
	}
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 24 ms 340 KB Output is correct
4 Correct 38 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct