Submission #522145

#	Time	Username	Problem	Language	Result	Execution time	Memory
522145		YuDabin	약속장소 정하기 (GCJ12KOR_appointment)	C++14	0 / 35	998 ms	262148 KiB

C

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e16;

int n, p, m;
vector<pair<int, int>> man;
vector<vector<pair<int, int>>> graph;
vector<int> ans;

void dijkstra(int i)
{
	vector<int> dist(n+1, -1);
	priority_queue<pair<int, int>> pq; pq.push({0, man[i].first});
	
	while(!pq.empty())
	{
		int here = pq.top().second, cost = -pq.top().first; pq.pop();
		if(dist[here] != -1) continue; dist[here] = cost;
		
		for(auto it : graph[here])
		{
			int there = it.first, ncost = cost + it.second * man[i].second;
			if(dist[there] != -1) continue;
			pq.push({-ncost, there});
		}
	}
	
	for(int j = 1; j <= n; j++)
	{
		if(dist[j] != -1)ans[j] = max(ans[j], dist[j]);
		else ans[j] = INF;
	}
}

int32_t main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	int T; cin >> T;
	for(int t = 1; t <= T; t++)
	{
		cin >> n >> p >> m;
		man.clear(); graph.clear();
		man.resize(p+1); graph.resize(n+1);
		for(int i = 1; i <= p; i++) cin >> man[i].first >> man[i].second;
		for(int i = 1; i <= m; i++)
		{
			int d, l; cin >> d >> l; vector<int> v(l+1);
			
			for(int j = 1; j <= l; j++)
			{
				cin >> v[j];
				for(int k = 1; k < j; k++)
				{
					graph[v[j]].push_back({v[k], (j - k) * d});
					graph[v[k]].push_back({v[j], (j - k) * d});
				}
			}
		}
		ans.resize(n+1, -1);
		for(int i = 1; i <= p; i++) dijkstra(i);
		
		int res = INF;
		for(int i = 1; i <= n; i++)
		{
			if(ans[i] != -1) res = min(res, ans[i]);
		}
		cout << "Case #" << t << ": " << (res == INF ? -1 : res) << '\n';
	}
}

Compilation message (stderr)

C.cpp: In function 'void dijkstra(long long int)':
C.cpp:20:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |   if(dist[here] != -1) continue; dist[here] = cost;
      |   ^~
C.cpp:20:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |   if(dist[here] != -1) continue; dist[here] = cost;
      |                                  ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25