답안 #522152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522152	2022-02-04T01:15:06 Z	YuDabin	약속장소 정하기 (GCJ12KOR_appointment)	C++14	0 / 35	3000 ms	12680 KB

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()
{
	int T; scanf("%lld", &T);
	for(int t = 1; t <= T; t++)
	{
		scanf("%lld%lld%lld", &n, &p, &m);
		
		man.clear(); graph.clear();
		man.resize(p+1); graph.resize(n+1);
		for(int i = 1; i <= p; i++) scanf("%lld%lld", &man[i].first, &man[i].second);
		for(int i = 1; i <= m; i++)
		{
			int d, l; scanf("%lld%lld", &d, &l); int prv, here;
			scanf("%lld", &prv);
			for(int j = 2; j <= l; j++)
			{
				scanf("%lld", &here);
				graph[here].push_back({prv, d});
				graph[prv].push_back({here, d});
				prv = here;
			}
		}
		ans.resize(n+1, -1);
		for(int i = 1; i <= p; i++) dijkstra(i);
		
		for(int i = 1; i <= n; i++) printf("%lld, ", ans[i]);
		puts("");
		
		int res = ans[1];
		for(int i = 1; i <= n; i++) res = min(res, ans[i]);
		printf("Case #%lld: %lld\n", t, (res == INF ? -1 : res));
	}
}

Compilation message

C.cpp: In function 'int32_t main()':
C.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  int T; scanf("%lld", &T);
      |         ~~~~~^~~~~~~~~~~~
C.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%lld%lld%lld", &n, &p, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
C.cpp:47:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   for(int i = 1; i <= p; i++) scanf("%lld%lld", &man[i].first, &man[i].second);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C.cpp:50:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |    int d, l; scanf("%lld%lld", &d, &l); int prv, here;
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~
C.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |    scanf("%lld", &prv);
      |    ~~~~~^~~~~~~~~~~~~~
C.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%lld", &here);
      |     ~~~~~^~~~~~~~~~~~~~~

Subtask #1

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	81 ms	552 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3070 ms	12680 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-