# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
984899 | 2024-05-17T08:04:24 Z | IUA_Hasin | 사이버랜드 (APIO23_cyberland) | C++17 | 44 ms | 26228 KB |
#include "cyberland.h" #include <bits/stdc++.h> #define endl "\n" #define yeap cout<<"YES"<<endl #define nope cout<<"NO"<<endl #define ll long long #define ld long double using namespace std; const ll M = 3e5+5; const ll INF = 5e16+69; vector<ll> ind0; vector<pair<ll, ll>> extra[M]; vector<pair<ll, ll>> graph[M]; vector<ll> dist(M, INF); ll vis[M]; void dijkstra(ll source){ set<pair<ll, ll>> s; s.insert({0, source}); dist[source] = 0; while(s.size()>0){ auto node = *s.begin(); ll v = node.second; ll v_dist = node.first; s.erase(s.begin()); if(vis[v]==0){ for(auto child : graph[v]){ ll v2 = child.first; ll wt = child.second; if((dist[v]+wt)<(dist[v2])){ dist[v2] = dist[v]+wt; s.insert({dist[v2], v2}); } } vis[v] = 1; } } } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { for(int i=0; i<=N; i++){ extra[i].clear(); graph[i].clear(); dist[i] = INF; vis[i] = 0; } ind0.clear(); for(int i=0; i<x.size(); i++){ ll a = x[i]; ll b = y[i]; ll wt = c[i]; if(a!=H && b!=H){ graph[a].push_back({b, wt}); graph[b].push_back({a, wt}); } else { extra[a].push_back({b, wt}); extra[b].push_back({a, wt}); } } // // for(int i=0; i<N; i++){ // for(int j=0; j<graph[i].size(); j++){ // cout << graph[i][j].first << " " << graph[i][j].second << endl; // } // cout<<endl; //} //okay // // for(int i=0; i<N; i++){ // for(int j=0; j<extra[i].size(); j++){ // cout << extra[i][j].first << " " << i<< endl; // } // cout<<endl; // } //okay for(int i=0; i<arr.size(); i++){ if(arr[i]==0){ ind0.push_back(i); } } // // for(int i=0; i<ind0.size(); i++){ // cout << ind0[i] << " "; // } // cout<<endl; //okay dijkstra(0); vector<ll> possibleind0; for(int i=0; i<ind0.size(); i++){ ll a = ind0[i]; //cout << a << " " << dist[a] << endl; if(dist[a]!=INF){ possibleind0.push_back(a); //cout<<a<<endl; } } // // for(int i=0; i<N; i++){ // cout << dist[i] << " "; // } // cout<<endl; //okay // // for(int i=0; i<possibleind0.size(); i++){ // cout << possibleind0[i] << " "; // } // cout<<endl; //okay for(int i=0; i<=N; i++){ for(int j=0; j<extra[i].size(); j++){ graph[i].push_back(extra[i][j]); } } // // for(int i=0; i<N; i++){ // for(int j=0; j<graph[i].size(); j++){ // cout << graph[i][j].first << " " << graph[i][j].second << endl; // } // cout<<endl; // } //okay for(int i=0; i<=N; i++){ //graph[i].clear(); dist[i] = INF; vis[i] = 0; } dijkstra(0); // // for(int i=0; i<N; i++){ // cout << dist[i] << " "; // } // cout<<endl; // ll ans = dist[H]; if(dist[H]==INF){ return -1; } else { for(int i=0; i<=N; i++){ //graph[i].clear(); dist[i] = INF; vis[i] = 0; } dijkstra(H); // // for(int i=0; i<N; i++){ // cout << dist[i] << " "; // } // cout<<endl; // //ans = INF; for(int i=0; i<possibleind0.size(); i++){ ll a = possibleind0[i]; ll temp = dist[a]; //cout << a << " " << temp << endl; ans = min(temp, ans); } return ans; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 19 ms | 16984 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 16984 KB | Correct. |
2 | Correct | 38 ms | 16984 KB | Correct. |
3 | Correct | 36 ms | 16984 KB | Correct. |
4 | Correct | 37 ms | 16988 KB | Correct. |
5 | Correct | 38 ms | 17192 KB | Correct. |
6 | Correct | 35 ms | 18012 KB | Correct. |
7 | Correct | 44 ms | 18008 KB | Correct. |
8 | Correct | 21 ms | 18776 KB | Correct. |
9 | Correct | 32 ms | 17076 KB | Correct. |
10 | Correct | 31 ms | 16988 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 17192 KB | Correct. |
2 | Correct | 36 ms | 17128 KB | Correct. |
3 | Correct | 34 ms | 17256 KB | Correct. |
4 | Correct | 33 ms | 17596 KB | Correct. |
5 | Correct | 33 ms | 16988 KB | Correct. |
6 | Correct | 12 ms | 17672 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 35 ms | 24148 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 17296 KB | Correct. |
2 | Correct | 30 ms | 17240 KB | Correct. |
3 | Correct | 32 ms | 17284 KB | Correct. |
4 | Correct | 32 ms | 18388 KB | Correct. |
5 | Correct | 25 ms | 16984 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 17344 KB | Correct. |
2 | Correct | 26 ms | 17244 KB | Correct. |
3 | Correct | 40 ms | 26228 KB | Correct. |
4 | Correct | 23 ms | 18012 KB | Correct. |
5 | Correct | 28 ms | 16988 KB | Correct. |
6 | Correct | 30 ms | 17240 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 17244 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 17244 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |