제출 #1115051

#제출 시각아이디문제언어결과실행 시간메모리
1115051AdamGSOlympic Bus (JOI20_ho_t4)C++17
5 / 100
1100 ms3500 KiB
#include <iostream> #include <functional> #include <vector> #include <queue> using namespace std; int main() { int n,m; cin >> n >> m; vector<int> U(m),V(m),C(m),D(m); for (int i=0; i<m; i++){ cin >> U[i] >> V[i] >> C[i] >> D[i]; } int64_t wyn=1e18; for (int i=0; i<m+1; i++){ vector<vector<pair<int64_t,int64_t>>> gr(n+1); int64_t akt; for (int j=0; j<m; j++){ if (j==i){ gr[V[j]].push_back({C[j],U[j]}); akt=D[j]; } else gr[U[j]].push_back({C[j],V[j]}); } /*cout << "\n===================================\n"; for (int j=1; j<n+1; j++){ cout << j << ":\n"; for (auto k:gr[j]) cout << k.second << ' ' << k.first << '\n'; cout << '\n'; } cout << "===================================\n"; cout << "===================================\n";*/ priority_queue<pair<int64_t,int64_t>,vector<pair<int64_t,int64_t>>,greater<pair<int64_t,int64_t>>> q; q.push({0,1}); vector<int64_t> odw(n+1,-1); while (q.size()){ pair<int64_t,int64_t> aktq=q.top(); q.pop(); if (odw[aktq.second]!=-1) continue; odw[aktq.second]=aktq.first; //cout << '\n' << aktq.first << ' ' << aktq.second << '\n'; for (auto j:gr[aktq.second]){ //cout << i << '\n'; //cout << j.first << ' ' << j.second << ' ' << odw[j.second] << '\n'; if (odw[j.second]==-1){ //cout << j.first << ' ' << j.second << '\n'; q.push({j.first+aktq.first,j.second}); } //else cout << j.first << ' ' << j.second << '\n'; } } //cout << '\n' << odw[n]+akt << '\n'; //if (odw[n]==-1) continue; q.push({0,n}); vector<int64_t> odw1(n+1,-1); while (q.size()){ pair<int64_t,int64_t> aktq=q.top(); q.pop(); if (odw1[aktq.second]!=-1) continue; odw1[aktq.second]=aktq.first; //cout << '\n' << aktq.first << ' ' << aktq.second << '\n'; for (auto j:gr[aktq.second]){ //cout << i << '\n'; //cout << j.first << ' ' << j.second << ' ' << odw1[j.second] << '\n'; if (odw1[j.second]==-1){ //cout << j.first << ' ' << j.second << '\n'; q.push({j.first+aktq.first,j.second}); } //else cout << j.first << ' ' << j.second << '\n'; } } //cout << 'a' << odw1[3]; if (i==m) akt=0; //cout << '\n' << odw[n] << ' ' <<akt << ' ' << odw1[1] << '\n'; if (odw1[1]==-1 or odw[n]==-1) continue; wyn=min(wyn,odw[n]+odw1[1]+akt); } if (wyn==1e18) cout << -1; else cout << wyn; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:76:35: warning: 'akt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         wyn=min(wyn,odw[n]+odw1[1]+akt);
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...