oj.uz

답안 #447903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447903 2021-07-28T05:38:50 Z Jasiekstrz Alias (COCI21_alias) C++17
70 / 70
 24 ms 460 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
const long long INF=1e18L+7;
int idit=0;
map<string,int> id;
vector<pair<int,int>> e[N+10];
long long d[N+10];
int getid(string x)
{
	if(id.find(x)==id.end())
		id[x]=++idit;
	return id[x];
}
void dijkstra(int x)
{
	priority_queue<pair<long long,int>> pq;
	d[x]=0;
	pq.emplace(0,x);
	while(!pq.empty())
	{
		auto [dd,y]=pq.top();
		pq.pop();
		if(d[y]!=-dd)
			continue;
		for(auto [v,c]:e[y])
		{
			if(d[v]>d[y]+c)
			{
				d[v]=d[y]+c;
				pq.emplace(-d[v],v);
			}
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m,q;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		string a,b;
		int c;
		cin>>a>>b>>c;
		e[getid(a)].emplace_back(getid(b),c);
	}
	cin>>q;
	while(q--)
	{
		string a,b;
		cin>>a>>b;
		for(int i=1;i<=n;i++)
			d[i]=INF;
		dijkstra(getid(a));
		if(d[getid(b)]==INF)
			cout<<"Roger\n";
		else
			cout<<d[getid(b)]<<"\n";
	}
	return 0;
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 16 ms 332 KB Output is correct
4 Correct 24 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct