Submission #1267953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267953		namhh	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	750 ms	5888 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e4+5;
int n,m,d[N][2],d1[N][2],d2[N][2],check[N],check1[N],mark[N];
pii trace[N][2];
struct edges{
	int id,v,w,p;
};
vector<edges>adj[N],adj1[N];
void dijkstra(int u, int type){
	for(int i = 1; i <= n; i++) d[i][type] = 1e18;
	d[u][type] = 0;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,u});
	while(!pq.empty()){
		auto[c,uu] = pq.top();
		pq.pop();
		if(c > d[uu][type]) continue;
		for(auto[id,v,w,p]: adj[uu]){
			if(d[v][type] > c+w){
				d[v][type] = c+w;
				trace[v][type] = {uu,id};
				pq.push({d[v][type],v});
			}
		}
	}
}
void dijkstra1(int u, int type){
	for(int i = 1; i <= n; i++) d1[i][type] = 1e18;
	d1[u][type] = 0;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,u});
	while(!pq.empty()){
		auto[c,uu] = pq.top();
		pq.pop();
		if(c > d1[uu][type]) continue;
		for(auto[id,v,w,p]: adj1[uu]){
			if(d1[v][type] > c+w){
				d1[v][type] = c+w;
				pq.push({d1[v][type],v});
			}
		}
	}
}
void redijkstra(int u, int type){
	for(int i = 1; i <= n; i++) d2[i][type] = 1e18;
	d2[u][type] = 0;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,u});
	while(!pq.empty()){
		auto[c,uu] = pq.top();
		pq.pop();
		if(c > d2[uu][type]) continue;
		for(auto[id,v,w,p]: adj[uu]){
			if(mark[id]) continue;
			if(d2[v][type] > c+w){
				d2[v][type] = c+w;
				pq.push({d2[v][type],v});
			}
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u,v,w,p;
		cin >> u >> v >> w >> p;
		adj[u].push_back({i,v,w,p});
		adj1[v].push_back({i,u,w,p});
	}
	dijkstra(1,0);
	int x = n;
	while(x != 1 && trace[x][0].fi != 0){
		pii cc = trace[x][0];
		check[cc.se] = 1;
		x = cc.fi;
	}
	dijkstra(n,1);
	x = 1;
	while(x != n && trace[x][1].fi != 0){
		pii cc = trace[x][1];
		check1[cc.se] = 1;
		x = cc.fi;
	}
	dijkstra1(1,0);
	dijkstra1(n,1);
	int ans = d[n][0]+d[1][1];
	int ans1 = d[n][0];
	int ans2 = d1[1][1];
	for(int i = 1; i <= n; i++){
		for(auto[id,v,w,p]: adj[i]){
			if(!check[id] && !check1[id]){
				ans = min({ans,d[1][1]+d[v][0]+d1[i][1]+w+p,d[n][0]+d[v][1]+d1[i][0]+w+p,d[v][0]+d1[i][1]+d[v][1]+d1[i][0]+2*w+p});
//				int x = min(d[n][0],d[v][0]+d1[i][1]+w+p);
//				int y = min(d1[1][1],d1[v][0]+d[i][1]+w+p);
//				cout << id << " " << d1[v][1] << " " << d[i][0] << " " << v << " " << i << "\n";
//				ans = min(ans,x+y);
////			    ans1 = min(ans1,d[v][0]+d1[i][1]+d[v][1]+d1[i][0]+2*w;
////			    ans2 = min(ans2,d[v][1]+d1[i][0]+w+p);
			}
			else{
				mark[id] = 1;
				adj[v].push_back({50001,i,w,p});
				redijkstra(1,0);
				redijkstra(n,1);
				ans = min(ans,d2[n][0]+d2[1][1]+p);
				mark[id] = 0;
				adj[v].pop_back();
			}
		}
	}
	//cout << ans1 << "\n";
//	int ans2 = d1[1][1];
//	for(int i = 1; i <= n; i++){
//		for(auto[id,v,w,p]: adj[i]){
//			if(!check1[id]) ans2 = min(ans2,d[v][1]+d1[i][0]+w+p);
//			else{
//				mark[id] = 1;
//				adj[v].push_back({-1,v,w,p});
//				redijkstra(n,1);
//				ans2 = min(ans2,d2[1][1]+p);
//				mark[id] = -1;
//				adj[v].pop_back();
//			}
//		}
//	}
	if(ans > 1e17) cout << -1;
	else cout << ans;
}
//                                                                                                    
//                                +.::=.                   .*: -.                                     
//                               --    :.                 =  -:--                                     
//                               .=    ..  .-=++*+++=:.  =      :                                     
//                                .=   ....:=%@@@@@*:    .     :.                                     
//                            .-+=..:   :.  .+##%##+.  .:     .+:                                     
//                         :*@**%* ..   :.               ::..:.:. --:                                 
//             .--.      +@@@@@%:   .==:                         .###@*                               
//            :--  -:  -:@@@@#                   -                 =@@@@#. .=  : +                    
//            .:    -=--==:                      ==      +-          :*%*++=   .:#                    
//             -.     .:.           .             +.      -*.   =@@.   .-.      .=                    
//               +=..  ..          --             .*       .#. +@#      -      :==*=                  
//             .=.+=::::           =.              =-        ##@+        :--+.#@%++%*                 
//            .++@@:        =      +               .%%%%@@@@@@@@@@@@@@%.    :-@#-: -@.                
//           :@@@@=        .+     .=                *#     .#@.=-             =@::-:@:                
//          :-@@%.         --     --                :@*.  .%#   +.          -  ** :=%. .*@#           
//    :-.  .-*-.           -:     +.                 %-=::@#    .*   :      -  :%- +%.+@+@@           
// .- :.  **:     +:       =      #                : =* =@#      -=  #     #@@@:-@ :*@@. %@           
//  -=:      ::  .* .=     +      #                =..@  .*.      +. *.    *#=.+%@*-%*   %@           
//   :=. :.. .:  +. -=    .+      #                -- #.   =-     .+ +:    =@+   .+-++   @%           
//       ++-=.   *  --    :=      #                :- +-    :*     =:+:    -@#  :@#*%@@@%@+           
//       *.     --  --    :=      #                .= #@#=.   +-   :=+:    :%@-#@@@#@+:@@#            
//       +      +.  --    :=      #                .= :=       .+.  +*.     *@@+=@-=@*-.#@.           
//       =      +   :=    .+      #                 = .=         .#.-@.     -+ .%# -@@=  @#           
//      .=     .=   .+     +      *.                = .+..         :*@      == =@. -#@#: @%           
//      .=     .=    *     +      =:               .=.**:   =--:     #    * *- %*  =*=@+#@:           
//      .=     :=    #     =.     .+ .             .= --.#@@@@@#@@@: *   -= #..@=  **:@@@:            
//       +     .=    +:    --      + #             := +@%:@#: -:%= ===   #..* .#@@%@+.@@+             
//       *     .=    .*    .=      -:-=            :- #= ++  =- =@. *:  .* -*:  :  . .@@%
//       *      +     *     +.     :- #            -- #  *: .@@  %- +   =- +-.- :.   .@@@.            
//       -:     =:    :=    .*      +.--           =:--  .*.:.:  # .=   +  *+    -   :@%@=            
//        +      *   *:+.    ==     .+ +.          +.#     .=-:=-  --  -- =+:    =   -@#%*            
//        +      -=   *==     *.     -=--         :+-=       :::   =:  +  %:.    =   %@+##            
//        .=      +:   +*-     +      +:+.        +:*.            .+  +: #.:. - .+  -@@=#%            
//         -.      =.  :=#-    :=      =:*    .-==#+-             +: =- +:-..- :%*  =@@:*%            
//         .-       +.  --+=           .**%+-:.                  -* +-:*:.:.  =@@* :-@@ *%            
//          -.       +=  -+==      -*#-          =-               ..        .%@#@=.--@* *%            
//           =.       .+: :+-*-=+:                                      +%+*@@%%@-= +@- *#            
//            -::=      :**=:                                          :@@@@@@%@@-  #@  #*            
//             -: +:       -                                          .@@#%@@%@@:  :@# .#+            
//              :- :#=     --                                        :@@@#@-=@#.   =@- .%=            
//                =:.@@%=   =#                   .+.=.              +@@@@* -*:     #%  :@:            
//                 .+ *@@@@@@@@*                                  :@@*@@@*        .@+  -@.            
//                   .+=%@*%@@@@@#:                             =@@@%:.:          +@:  +%             
//                     .=%@%#@@@@##@*:                       =%@@@#:              @#   ##             
//                         :#@%@@@@#@@@@+                 :*. @:                 =@-  .@+             
//                                 .+@%#%@@:=-..       .=:    %*==+.             @%   -@-             
//                                  =.    =:     :-:.::     .-- .= -:           =@-    -              
//                                 .-  :-. ::              .-     =-:                                 
//       .=+-.=-.*-                 =       -..+*:     .-:.-       =                  .+*#   ....     
//      =.         -=               -:      ..    -.  +.  -.      +.                -+   -*=:    +.   
//     .-            +-              *             -.*           #+               .+   =.        :=   
//     :-             --=*:        -+ *=           -#           -  -##+-..    .:+#:              +.   
//     :-             =    --=:==+*.    =:         .:     .=              =**=    =             .+    
//     .=             +     =--              :-          .=.               --    .-             =     
//      =             .-    --:               .-+*@%*#                     +.    +             :-     
//       +             +-   -:-           :*@@@@@@*@#*@@%*=:              =:    -              -.     
//       .*            -    ::+         =@@@@#-.-@@%%@@+=%@@@%=          -::   =              :-
//        .+           :.    +-.       #@@@=   +@@@-#@@%.   +@@@+       .:=   .-             +:       
//         .--.         -.   :=-      :@@+   :@@@@# =@@@#     -%@#      -=    ::         :-+-         
//           * -         +    --.      +@@#=%@@@@@. :@@@@%     :%@     :=    =.          -=+          
//            .-**-      -.    --       .%@@@@+%@+   @@+%@@*-+@@@.    :=.   -          :+*-           
//                   :===-==.  .-=            *@%    *@= +%%##=.     :=:   :. .::-==-.                
//                           .::-=+=+=-:.     #%:    -#:           .-*#+===-:.                        
//                                           ..::---====---::.

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63