oj.uz

Submission #131945

# Submission time Handle Problem Language Result Execution time Memory
131945 2019-07-18T05:26:50 Z 이온조(#3189) Wild Boar (JOI18_wild_boar) C++14
0 / 100
 2 ms 504 KB 
#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])});
				}
			}
		}
		printf("%d", ans);
	}
	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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -