제출 #923348

#제출 시각아이디문제언어결과실행 시간메모리
923348NotLinuxOlympic Bus (JOI20_ho_t4)C++17
0 / 100
367 ms6888 KiB
// put it before the include #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //author : FatihCihan #include <bits/stdc++.h> using namespace std; #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() #define int long long const int inf = 1e18 + 7; void solve(){ int n,m; cin >> n >> m; vector < vector < pair < int , int > > > graph(n+1) , igraph(n+1); array < int , 4 > edge[m]; bool is_in_path[m]; memset(is_in_path , 0 , sizeof(is_in_path)); for(int i = 0;i<m;i++){ cin >> edge[i][0] >> edge[i][1] >> edge[i][2] >> edge[i][3]; graph[edge[i][0]].push_back({edge[i][1] , i}); igraph[edge[i][1]].push_back({edge[i][0] , i}); } auto eval = [&](int st , vector < vector < pair < int , int > > > G , int forbidden){ vector < int > vis(n+1 , inf); vector < pair < int , int > > pq(n+1 , {inf , inf}); pq[st] = {0,-1}; // cout << "forbidden : " << forbidden << endl; while(true){ int tmp = -1; pair < int , int > val = {inf,inf}; for(int i = 1;i<=n;i++){ if(vis[i] == inf and val > pq[i]){ tmp = i; val = pq[i]; } } if(tmp == -1 or val.first == inf)break; // cout << "bfs : " << tmp << " " << val.first << " " << val.second << endl; vis[tmp] = val.first; if(val.second != -1 and forbidden == -1){ is_in_path[val.second] = 1; } for(int i = 0;i<sz(G[tmp]);i++){ if(G[tmp][i].second != forbidden){ array < int , 4 > ed = edge[G[tmp][i].second]; pq[ed[1]] = min(pq[ed[1]] , {val.first + ed[2] , G[tmp][i].second}); } } } // cout << st << " : ";for(int i = 1;i<=n;i++)cout << vis[i] << " ";cout << endl; return vis; }; vector < int > from1 = eval(1 , graph , -1); vector < int > fromn = eval(n , graph , -1); vector < int > to1 = eval(1 , igraph , -1); vector < int > ton = eval(n , igraph , -1); int ans = from1[n] + fromn[1]; int sayac = 0; for(int i = 0;i<m;i++){ // cout << "edge : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl; int r1 , r2; if(is_in_path[i]){ // cout << "sayac : " << sayac << " " << i << endl; sayac++; // cout << "special : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl; vector < int > tfrom1 = eval(1 , graph , i); // cout << "tfrom1 : ";for(int i = 1;i<=n;i++)cout << tfrom1[i] << " ";cout << endl; vector < int > tfromn = eval(n , graph , i); // cout << "tfromn : ";for(int i = 1;i<=n;i++)cout << tfromn[i] << " ";cout << endl; vector < int > tto1 = eval(1 , igraph , i); // cout << "tto1 : ";for(int i = 1;i<=n;i++)cout << tto1[i] << " ";cout << endl; vector < int > tton = eval(n , igraph , i); // cout << "tton : ";for(int i = 1;i<=n;i++)cout << tton[i] << " ";cout << endl; r1 = min(tfrom1[n] , tfrom1[edge[i][1]] + edge[i][2] + tton[edge[i][0]]);//gidis r2 = min(tfromn[1] , tfromn[edge[i][1]] + edge[i][2] + tto1[edge[i][0]]);//donus // cout << "r : " << r1 << " " << r2 << endl; } else{ // cout << "ordinary : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl; r1 = min(from1[n] , from1[edge[i][1]] + edge[i][2] + ton[edge[i][0]]);//gidis r2 = min(fromn[1] , fromn[edge[i][1]] + edge[i][2] + to1[edge[i][0]]);//donus // cout << "r : " << r1 << " " << r2 << endl; } // cout << "######" << endl; ans = min(ans , edge[i][3] + r1 + r2); } cout << (ans >= inf ? -1 : ans) << endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase = 1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...