Submission #377280

#	Time	Username	Problem	Language	Result	Execution time	Memory
377280		YJU	Robot (JOI21_ho_t4)	C++14	0 / 100	532 ms	49752 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

map<ll,ll> cnt[N];
ll n,m,x,y,c,p;
ll u[N],dis[N];
vector<pair<ll,pll> > v[N];
priority_queue<pll,vector<pll>,greater<pll> > pq;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,m){
		cin>>x>>y>>c>>p;
		cnt[x][c]+=p;cnt[y][c]+=p;
		v[x].pb(mp(y,mp(c,p)));
		v[y].pb(mp(x,mp(c,p)));
	}
	REP1(i,n){
		u[i]=INF;
		if(SZ(cnt[i])<m)u[i]=0;
		for(auto j:cnt[i])u[i]=min(u[i],j.Y);
	}
	REP1(i,n)dis[i]=INF;
	pq.push(mp(dis[1]=0,1));
	while(SZ(pq)){
		y=pq.top().X,x=pq.top().Y;
		pq.pop();
		if(y>dis[x])continue;
		for(auto i:v[x]){
			ll ec=min(u[x]+i.Y.Y,cnt[x][i.Y.X]-i.Y.Y);
			if(ec+y<dis[i.X]){
				pq.push(mp(dis[i.X]=ec+y,i.X));
			}
		}
	}
	cout<<(dis[n]==INF?-1:dis[n])<<"\n";
	return 0;
}

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