Untitled
??unknown
c_cpp
2 years ago
2.3 kB
7
Indexable
#include <bits/stdc++.h> #define pii pair<ll, ll> // 생성자 ok typedef long long ll; using namespace std; const ll MAX = 100001; ll C[MAX], D[MAX], TD[MAX]; vector<pii> G[MAX], TG[MAX]; int indegree[100001]; void Dijstra(int cur){ fill(D, D + MAX, 1E18); D[cur] = 0; priority_queue<pii, vector<pii>, greater<pii>> PQ; PQ.emplace(0,cur); while(!PQ.empty()){ auto [cd, cur] = PQ.top(); PQ.pop(); if(cd > D[cur]) continue; for(auto & [next, nd] : G[cur]){ if(D[next]<=D[cur]+nd) continue; PQ.emplace(D[next] = D[cur] + nd, next); } } } void topologcialSort(ll &n, ll & target){ queue<int> que; ll ret = 0; for(int i = 1 ;i<=n;i++){ if(indegree[i]==0){ que.push(i); TD[i] = C[i]; } } while(!que.empty() && indegree[target]){ int x = que.front(); que.pop(); for(int j = 0; j< TG[x].size();j++){ int next = TG[x][j].first; TD[next] = max(TD[next], TD[x] + C[next]); if(--indegree[next]==0){ que.push(next); } } } return; } int main(void){ ios::sync_with_stdio(false);cin.tie(0); ll N, M; cin >> N; for(int i = 1;i<=N;i++) cin >> C[i]; cin >> M; for(int j = 1;j<=M;j++){ ll u, v, d; cin >> u >> v >> d; G[u].emplace_back(v,d); G[v].emplace_back(u,d); } ll s,t; cin >> s >> t; Dijstra(s); // s를 기준으로 나머지 vertex의 최단거리를 D에 기록했음 for(int i = 1; i <= N; i++){ sort(G[i].begin(), G[i].end()); // 가장 작은 것부터 시작 for(auto &[next, nd] : G[i]){ if(D[next] + nd != D[i]) continue; // 현재부터 다음 dist를 더했을 때 같아야 된다. TG[next].emplace_back(i, C[i]); // i -> next -> next_next indegree[next]++; break; } } for(int i = 1;i<=N;i++) { cout << D[i] << " "; } cout << endl; topologcialSort(N,t); for(int i = 1;i<=N;i++) { cout << TD[i] << " "; // TD[i] = C[i] } cout << endl; if(D[t] != 1E18){ cout << D[t] << " " << TD[t] << endl; } else{ cout << -1 << endl; } }
Editor is loading...