# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1126041 | ardadut | 악어의 지하 도시 (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
using namespace std;
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout */
const ll INF = 1e15;
inline int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
vector<vector<pair<ll,ll>>> adj(n+1);
for(ll i = 0 ; i < m ; i++){
adj[r[i][0]].pb({r[i][1],l[i]});
adj[r[i][1]].pb({r[i][0],l[i]});
}
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
vector<pair<ll,ll>> dist(n+1);
for(ll i = 0 ; i < n ; i++){
dist[i] = {INF,INF};
}
for(ll i = 0 ; i < k ; i++){
pq.push({0,p[i]});
dist[p[i]] = {0,0};
}
while(!pq.empty()){
ll node = pq.top().second;
ll weight = pq.top().first;
pq.pop();
cout << "node : " << node << " weight : " << weight << endl;
if(weight > dist[node].second) continue;
cout << "pq giden : ";
if(weight < dist[node].first){
cout << "tur : 1 " << endl;
dist[node] = {weight,dist[node].first};
}else{
cout << "tur : 2 " << endl;
dist[node].second = weight;
for(auto go : adj[node]){
cout << go.first << " ";
pq.push({dist[node].second + go.second,go.first});
}
}
cout << endl << endl;
}
return dist[0].second;
}