Submission #1575435


Source Code Expand

#include <iostream>
#include <queue>
#include <functional>
#include <vector>
using namespace std;

int n, m;
int s, t;
vector<int> edgeTo[1000];
vector<int> edgeCost[1000];

int minDistS[1000];
int minDistT[1000];

void dijkstra(int start, int minDist[]) {
	typedef pair<int, int> P;	//cost, pos
	priority_queue<P, vector<P>, greater<P>> que;	//cost昇順でほげほげ
	int i;
	
	for (i = 0; i < n; i++) minDist[i] = 1145141919;
	
	que.push(P(0, start));
	minDist[start] = 0;
	while (!que.empty()) {
		P now = que.top(); que.pop();
		int c = now.first;
		int v = now.second;
		
		for (i = 0; i < edgeTo[v].size(); i++) {
			int nextV = edgeTo[v][i];
			if (minDist[nextV] > c + edgeCost[v][i]) {
				minDist[nextV] = c + edgeCost[v][i];
				que.push(P(minDist[nextV], nextV));
			}
		}
	}
}

int main() {
	int i;

	cin >> n >> m;
	cin >> s >> t;
	s--; t--;
	
	for (i = 0; i < m; i++) {
		int from, to, c;
		cin >> from >> to >> c;
		from--;
		to--;
		edgeTo[from].push_back(to);
		edgeTo[to].push_back(from);
		edgeCost[from].push_back(c);
		edgeCost[to].push_back(c);
	}
	
	dijkstra(s, minDistS);
	dijkstra(t, minDistT);
	
	for (int u = 0; u < n; u++) {
		if (u == s || u == t) continue;
		if (minDistS[u] == minDistT[u]) {
			cout << u + 1 << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Submission Info

Submission Time
Task C - 身体バランス
User startcpp
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1374 Byte
Status WA
Exec Time 9 ms
Memory 640 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 50
WA × 4
Set Name Test Cases
All 00-sample-00, 00-sample-01, corner-case-01, corner-case-02, corner-case-03, largest-00, largest-01, largest-02, largest-03, largest-04, largest-05, random-00-0934, random-01-0457, random-02-0288, random-03-0873, random-04-0364, random-05-0053, random-06-0613, random-07-0729, random-08-0061, random-09-0645, random-10-0095, random-11-0369, random-12-0115, random-13-0260, random-14-0033, random-15-0579, random-16-0713, random-17-0336, random-18-0297, random-19-0826, random-20-0742, random-21-0264, random-22-0507, random-23-0502, random-24-0750, random-25-0721, random-26-0043, random-27-0348, random-28-0756, random-29-0647, random-30-0854, random-31-0554, random-32-0632, random-33-0776, random-34-0165, random-35-0695, random-36-0136, random-37-0831, random-38-0284, random-39-0610, random-40-0421, sample-00, sample-01
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
corner-case-01 WA 1 ms 256 KB
corner-case-02 WA 2 ms 384 KB
corner-case-03 WA 2 ms 384 KB
largest-00 AC 9 ms 640 KB
largest-01 AC 9 ms 640 KB
largest-02 AC 9 ms 640 KB
largest-03 AC 9 ms 640 KB
largest-04 AC 9 ms 640 KB
largest-05 AC 8 ms 640 KB
random-00-0934 AC 9 ms 640 KB
random-01-0457 AC 9 ms 640 KB
random-02-0288 AC 8 ms 640 KB
random-03-0873 AC 9 ms 640 KB
random-04-0364 AC 9 ms 640 KB
random-05-0053 AC 2 ms 384 KB
random-06-0613 AC 9 ms 640 KB
random-07-0729 AC 9 ms 640 KB
random-08-0061 AC 2 ms 384 KB
random-09-0645 AC 8 ms 640 KB
random-10-0095 AC 1 ms 256 KB
random-11-0369 AC 4 ms 384 KB
random-12-0115 AC 2 ms 384 KB
random-13-0260 AC 4 ms 384 KB
random-14-0033 AC 1 ms 256 KB
random-15-0579 WA 3 ms 384 KB
random-16-0713 AC 9 ms 640 KB
random-17-0336 AC 9 ms 640 KB
random-18-0297 AC 8 ms 640 KB
random-19-0826 AC 9 ms 640 KB
random-20-0742 AC 9 ms 640 KB
random-21-0264 AC 8 ms 512 KB
random-22-0507 AC 9 ms 640 KB
random-23-0502 AC 9 ms 640 KB
random-24-0750 AC 9 ms 640 KB
random-25-0721 AC 9 ms 640 KB
random-26-0043 AC 2 ms 384 KB
random-27-0348 AC 9 ms 640 KB
random-28-0756 AC 9 ms 640 KB
random-29-0647 AC 9 ms 640 KB
random-30-0854 AC 9 ms 640 KB
random-31-0554 AC 9 ms 640 KB
random-32-0632 AC 7 ms 512 KB
random-33-0776 AC 9 ms 640 KB
random-34-0165 AC 8 ms 512 KB
random-35-0695 AC 4 ms 384 KB
random-36-0136 AC 6 ms 512 KB
random-37-0831 AC 9 ms 640 KB
random-38-0284 AC 8 ms 640 KB
random-39-0610 AC 9 ms 640 KB
random-40-0421 AC 9 ms 512 KB
sample-00 AC 1 ms 256 KB
sample-01 AC 1 ms 256 KB