답안 #131946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131946	2019-07-18T05:28:39 Z	이온조(#3189)	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	7 ms	1656 KB

wild_boar

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

struct info {
	int v, p, x, i;
};

bool operator <(info PP, info QQ) {
	return PP.v > QQ.v;
}

int N, M, T, L;
vector<pii> adj[2009];
int X[100009], P[100009], Q[100009];
int D[11][11][100009];

int main() {
 	scanf("%d%d%d%d",&N,&M,&T,&L);
	for(int i=0; i<M; i++) {
		int u, v, w; scanf("%d%d%d",&u,&v,&w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for(int i=1; i<=L; i++) scanf("%d",&X[i]);
	for(int i=1; i<=T; i++) scanf("%d%d",&P[i],&Q[i]);
	if(T == 1) {
		X[P[1]] = Q[1];
		for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) for(int k=1; k<=L; k++) D[i][j][k] = 1e9;
		priority_queue<info> pq; pq.push({0, X[1], X[1], 1});
		D[X[1]][X[1]][1] = 0;
		int ans = 1e9;
		while(pq.size()) {
			info n = pq.top(); pq.pop();
			if(n.v != D[n.p][n.x][n.i]) continue;
			if(n.i == L) ans = min(ans, n.v);
			for(auto& it: adj[n.x]) {
				int &th = D[n.x][it.first][n.i + (it.first == X[n.i+1])];
				if(th > n.v + it.second && it.first != n.p) {
					th = n.v + it.second;
					pq.push({th, n.x, it.first, n.i + (it.first == X[n.i+1])});
				}
			}
		}
		if(ans == 1e9) puts("-1");
		else printf("%d", ans);
	}
	else assert(0);
	return 0;
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&N,&M,&T,&L);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:22:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d%d%d",&u,&v,&w);
                ~~~~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=L; i++) scanf("%d",&X[i]);
                          ~~~~~^~~~~~~~~~~~
wild_boar.cpp:27:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=T; i++) scanf("%d%d",&P[i],&Q[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	508 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	632 KB	Output is correct
7	Correct	2 ms	632 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	632 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	760 KB	Output is correct
13	Correct	2 ms	760 KB	Output is correct
14	Correct	2 ms	760 KB	Output is correct
15	Correct	2 ms	888 KB	Output is correct
16	Correct	2 ms	760 KB	Output is correct
17	Correct	2 ms	764 KB	Output is correct
18	Correct	2 ms	760 KB	Output is correct
19	Correct	2 ms	888 KB	Output is correct
20	Correct	2 ms	888 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	3 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	508 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	632 KB	Output is correct
7	Correct	2 ms	632 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	632 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	760 KB	Output is correct
13	Correct	2 ms	760 KB	Output is correct
14	Correct	2 ms	760 KB	Output is correct
15	Correct	2 ms	888 KB	Output is correct
16	Correct	2 ms	760 KB	Output is correct
17	Correct	2 ms	764 KB	Output is correct
18	Correct	2 ms	760 KB	Output is correct
19	Correct	2 ms	888 KB	Output is correct
20	Correct	2 ms	888 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	3 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Runtime error	7 ms	1656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	508 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	632 KB	Output is correct
7	Correct	2 ms	632 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	632 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	760 KB	Output is correct
13	Correct	2 ms	760 KB	Output is correct
14	Correct	2 ms	760 KB	Output is correct
15	Correct	2 ms	888 KB	Output is correct
16	Correct	2 ms	760 KB	Output is correct
17	Correct	2 ms	764 KB	Output is correct
18	Correct	2 ms	760 KB	Output is correct
19	Correct	2 ms	888 KB	Output is correct
20	Correct	2 ms	888 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	3 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Runtime error	7 ms	1656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	508 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	632 KB	Output is correct
7	Correct	2 ms	632 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	632 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	760 KB	Output is correct
13	Correct	2 ms	760 KB	Output is correct
14	Correct	2 ms	760 KB	Output is correct
15	Correct	2 ms	888 KB	Output is correct
16	Correct	2 ms	760 KB	Output is correct
17	Correct	2 ms	764 KB	Output is correct
18	Correct	2 ms	760 KB	Output is correct
19	Correct	2 ms	888 KB	Output is correct
20	Correct	2 ms	888 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	3 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Runtime error	7 ms	1656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Halted	0 ms	0 KB	-

답안 #131946

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0