結果
問題 | No.416 旅行会社 |
ユーザー | tnakao0123 |
提出日時 | 2016-09-03 01:58:31 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 408 ms / 4,000 ms |
コード長 | 1,831 bytes |
コンパイル時間 | 896 ms |
コンパイル使用メモリ | 97,404 KB |
実行使用メモリ | 25,400 KB |
最終ジャッジ日時 | 2023-08-21 10:03:42 |
合計ジャッジ時間 | 5,926 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 106 ms
15,724 KB |
testcase_01 | AC | 3 ms
6,104 KB |
testcase_02 | AC | 3 ms
5,864 KB |
testcase_03 | AC | 3 ms
6,124 KB |
testcase_04 | AC | 4 ms
5,884 KB |
testcase_05 | AC | 3 ms
5,800 KB |
testcase_06 | AC | 3 ms
5,788 KB |
testcase_07 | AC | 4 ms
5,928 KB |
testcase_08 | AC | 6 ms
6,032 KB |
testcase_09 | AC | 16 ms
7,336 KB |
testcase_10 | AC | 126 ms
15,680 KB |
testcase_11 | AC | 124 ms
15,616 KB |
testcase_12 | AC | 129 ms
15,640 KB |
testcase_13 | AC | 105 ms
15,612 KB |
testcase_14 | AC | 397 ms
25,364 KB |
testcase_15 | AC | 400 ms
25,400 KB |
testcase_16 | AC | 408 ms
25,008 KB |
testcase_17 | AC | 402 ms
25,276 KB |
testcase_18 | AC | 401 ms
25,256 KB |
testcase_19 | AC | 259 ms
20,876 KB |
testcase_20 | AC | 258 ms
20,552 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 416.cc: No.416 旅行会社 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_M = 100000; const int INF = 1 << 30; /* typedef */ typedef pair<int,int> pii; typedef map<pii,int> mpii; typedef vector<pii> vpii; /* global variables */ mpii es; vpii nbrs[MAX_N]; int dists[MAX_N]; /* subroutines */ /* main */ int main() { int n, m, qn; scanf("%d%d%d", &n, &m, &qn); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; es[pii(u, v)] = -1; } for (int i = 0; i < qn; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; es[pii(u, v)] = qn - i; } for (mpii::iterator mit = es.begin(); mit != es.end(); mit++) { const int &u = mit->first.first, &v = mit->first.second, &c = mit->second; nbrs[u].push_back(pii(v, c)); nbrs[v].push_back(pii(u, c)); } for (int i = 0; i < n; i++) dists[i] = INF; dists[0] = -1; priority_queue<pii> q; q.push(pii(1, 0)); while (! q.empty()) { pii u = q.top(); q.pop(); int ud = -u.first, &ui = u.second; vpii &nbru = nbrs[ui]; for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int &vi = vit->first, vd = max(ud, vit->second); if (dists[vi] > vd) { dists[vi] = vd; q.push(pii(-vd, vi)); } } } for (int i = 1; i < n; i++) { if (dists[i] >= INF) puts("0"); else if (dists[i] < 0) puts("-1"); else printf("%d\n", qn - dists[i] + 1); } return 0; }