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 |
|
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 |