#include #include #include #include #include #include #define endl '\n' #define pll pair #define vpll vector> #define SIZE 501 #define INF 20'000'001 using namespace std; vpll dijk(vpll city[SIZE], int start_p, int end_p); signed main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while (true) { int city_cnt, road_cnt, start_p, end_p; cin >> city_cnt >> road_cnt; if (city_cnt == 0 && road_cnt == 0) break; cin >> end_p >> start_p; vpll city[SIZE]; for (int x = 0; x < road_cnt; x++) { int s, e, p; cin >> s >> e >> p; city[s].push_back({ p,e }); } vpll remove = dijk(city, start_p, end_p); for (auto x : remove) { for (int y = 0; y < city[x.first].size(); y++) { if (city[x.first][y].second == x.second) city[x.first][y].first = INF; } } int dist[SIZE]; fill_n(dist, SIZE, INF); priority_queue, vector>, greater<>> pq; dist[start_p] = 0; pq.push({ 0,start_p }); while (!pq.empty()) { int cur_l = pq.top().second; int cur_price = pq.top().first; pq.pop(); if (dist[cur_l] < cur_price) continue; for (auto x : city[cur_l]) { int next_l = x.second; int next_price = cur_price + x.first; if (dist[next_l] > next_price) { dist[next_l] = next_price; pq.push({ next_price,next_l }); } } } if (dist[end_p] == INF) cout << -1 << endl; else cout << dist[end_p] << endl; } return 0; } vpll dijk(vpll city[SIZE], int start_p, int end_p) { vector ret[SIZE]; int dist[SIZE]; fill_n(dist, SIZE, INF); priority_queue, vector>, greater<>> pq; dist[start_p] = 0; pq.push({ 0,start_p }); while (!pq.empty()) { int cur_l, cur_price; cur_price = pq.top().first; cur_l = pq.top().second; pq.pop(); if (dist[cur_l] < cur_price) continue; for (auto x : city[cur_l]) { int next_l, next_price; next_l = x.second; next_price = cur_price + x.first; if (dist[next_l] > next_price) { ret[next_l].clear(); dist[next_l] = next_price; pq.push({ next_price,next_l }); ret[next_l].push_back(cur_l); } else if (dist[next_l] == next_price) ret[next_l].push_back(cur_l); } } vpll remove; queue q; q.push(end_p); while (!q.empty()) { int cur = q.front(); q.pop(); for (auto x : ret[cur]) { int next = x; remove.push_back({ next,cur }); q.push(next); } } return remove; }

제출 #11427

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: