Submission #485598

#	Time	Username	Problem	Language	Result	Execution time	Memory
485598		PoPularPlusPlus	Robot (JOI21_ho_t4)	C++17	0 / 100	3126 ms	1066304 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

const int N = 100002;
vector<pair<ll,pair<int,int>>> adj[N];
ll dis[N];

void Dijkstra(ll e){
	 priority_queue< pair<ll,ll>, vector <pair<ll,ll>> , greater<pair<ll,ll>> > pq; 
	 dis[e]=0;
	 pq.push({0,e});
	 while(!pq.empty()){
		 ll node = pq.top().second,ww=pq.top().first;
		 pq.pop();
		 if(dis[node] < ww)continue;
		 for(int i = 0; i < (int)adj[node].size(); i++){
			 int j = i + 1;
			 ll sum = 0 , mx = 0;
			 while(j < (int)adj[node].size() && adj[node][i].vf == adj[node][j].vf){
				 ll w =  adj[node][j].vs.vs;
				 sum += w;
				 mx = max(mx , w);
				 int cur = adj[node][j].vs.vf;
				 if(dis[cur] > dis[node] + w){
					dis[cur] = dis[node] + w;
					pq.push({dis[cur] , cur});
				}
				j++;
			 }
			 if(j == i + 1){
				 if(dis[adj[node][i].vs.vf] > dis[node]){
					 dis[adj[node][i].vs.vf] = dis[node];
					 pq.push({dis[adj[node][i].vs.vf] , adj[node][i].vs.vf});
				 }
			 }
			 else {
				 ll w = adj[node][i].vs.vs;
				 if(dis[adj[node][i].vs.vf] > dis[node] + w){
					 dis[adj[node][i].vs.vf] = dis[node] + w;
					 pq.push({dis[adj[node][i].vs.vf] , adj[node][i].vs.vf});
				 }
				 sum -= mx;
				 for(int k = i; k < j; k++){
					 if(dis[adj[node][k].vs.vf] > dis[node] + sum){
						 pq.push({dis[adj[node][k].vs.vf] , adj[node][k].vs.vf});
					 }
				 }
			 }
			 i = j - 1;
			/* ll w = i.second;
			 if(dis[i.first] > dis[node] + w){
				 dis[i.first] = dis[node] + w;
				 pq.push({dis[i.first],i.first});
			 }*/
		 }
	 }
}

void solve(){
	int n , m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		ll a , b , c , d;
		cin >> a >> b >> c >> d;
		adj[a].pb(mp(c,mp(b,d)));
		adj[b].pb(mp(c,mp(a,d)));
	}
	for(int i = 1; i <= n; i++){
		sort(all(adj[i]));
		dis[i] = 1e18;
	}
	Dijkstra(1);
	cout << (dis[n] >= 1e18 ? -1 : dis[n]) << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42