Submission #447903

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447903	2021-07-28T05:38:50 Z	Jasiekstrz	Alias (COCI21_alias)	C++17	70 / 70	24 ms	460 KB

alias

#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

#	Verdict	Execution time	Memory	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