結果
問題 | No.416 旅行会社 |
ユーザー |
![]() |
提出日時 | 2016-08-26 23:54:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 512 ms / 4,000 ms |
コード長 | 1,478 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 104,504 KB |
実行使用メモリ | 31,032 KB |
最終ジャッジ日時 | 2024-12-14 19:57:21 |
合計ジャッジ時間 | 7,090 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream> #include <fstream> #include <vector> #include <cstring> #include <string> #include <algorithm> #include <iomanip> #include <map> #include <queue> #include <functional> using namespace std; typedef long long W; const W INF = 1 << 25; struct edge { int to; W cost; }; typedef pair<W, int> P; typedef vector<vector <edge > > Graph; void dijkstra(int s, const Graph& G, vector<W>& d) { priority_queue<P> que; fill(d.begin(), d.end(), -1); d[s] = INF; que.push(P(INF, s)); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(d[v] > p.first) continue; for(int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if(d[e.to] < min(d[v], e.cost)) { d[e.to] = min(d[v], e.cost); que.push(P(d[e.to], e.to)); } } } } const int MAX = 100010; int N, M, Q; int main() { cin.tie(0); ios::sync_with_stdio(false); map<P, int> m; cin >> N >> M >> Q; for(int i = 0; i < M; i++) { int A, B; cin >> A >> B; m[P(A, B)] = INF; } for(int i = 1; i <= Q; i++) { int A, B; cin >> A >> B; m[P(A, B)] = i; } Graph G(N); for(auto val : m) { int A = val.first.first, B = val.first.second; int T = val.second; G[A - 1].push_back(edge{ B - 1, T }); G[B - 1].push_back(edge{ A - 1, T }); } vector<W> d(N); dijkstra(0, G, d); for(int i = 1; i < N; i++) { if(d[i] == INF) { cout << -1 << endl; } else if(d[i] == -1) { cout << 0 << endl; } else { cout << d[i] << endl; } } }