제출 #1045503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045503		vjudge1	Olympic Bus (JOI20_ho_t4)	C++14	32 / 100	495 ms	4808 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
inline long long read(){
	long long c=1,f=0;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			c=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		f=f*10+(ch-'0');
		ch=getchar();
	}
	return c*f;
}
inline void write(__int128 x){
	if(x<0){
		putchar('-');
		x=-1*x;
	}
	if(x>9){
		write(x/10);
	}
	putchar('0'+x%10);
	return;
}
struct node{
	long long id;
	long long d;
	bool operator > (node b)const{
		return d>b.d;
	}
}; 
priority_queue<node,vector<node>,greater<node> >q;
long long n,m,w[50005],ne[50005],h[205],tot,d[50005],f[205],g[205]; 
long long w1[50005],ne1[50005],h1[205],tot1,d1[50005],v[50005];
long long pref[205],preg[205],ans[50005],dis1[205],dis2[205],minn;
bool vis[50005],flag[205],isok[205];
void add(long long a,long long b,long long c){
	w[++tot]=b;
	d[tot]=c;
	ne[tot]=h[a];
	h[a]=tot;
	return;
}
void add1(long long a,long long b,long long c){
	w1[++tot1]=b;
	d1[tot1]=c;
	ne1[tot1]=h1[a];
	h1[a]=tot1;
	return;
}
void dijstra(long long u){
	for(int i=1;i<=n;i++){
		f[i]=1e18;
		flag[i]=false;
	}
	f[u]=0;
	node temp;
	temp.id=u;
	temp.d=0;
	q.push(temp);
	while(!q.empty()){
		node p=q.top();
		q.pop();
		if(flag[p.id]){
			continue;
		}
		flag[p.id]=true;
		for(int i=h[p.id];i;i=ne[i]){
			if(isok[i]){
				continue;
			}
			temp.id=w[i];
			temp.d=p.d+d[i];
			if(f[temp.id]>temp.d){
				f[temp.id]=temp.d;
				pref[temp.id]=i;
				q.push(temp);
			}
		}
	}
	return;
}
void dijstra1(long long u){
	for(int i=1;i<=n;i++){
		g[i]=1e18;
		flag[i]=false;
	}
	g[u]=0;
	node temp;
	temp.id=u;
	temp.d=0;
	q.push(temp);
	while(!q.empty()){
		node p=q.top();
		q.pop();
		if(flag[p.id]){
			continue;
		}
		flag[p.id]=true;
		for(int i=h1[p.id];i;i=ne1[i]){
			if(isok[i]){
				continue;
			}
			temp.id=w1[i];
			temp.d=p.d+d1[i];
			if(g[temp.id]>temp.d){
				g[temp.id]=temp.d;
				preg[temp.id]=i;
				q.push(temp);
			}
		}
	}
	return;
}
int main(){
//	freopen("sets.in","r",stdin);
//	freopen("sets.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	n=read();m=read();
	for(int i=1;i<=m;i++){
		long long a,b,c;
		a=read();b=read();c=read();v[i]=read();
		add(a,b,c);
		add1(b,a,c);
	}
	dijstra(1);
	dijstra1(n);
	minn=f[n];
	for(int i=1;i<=n;i++){
		dis1[i]=f[i];dis2[i]=g[i];
	}
	for(int i=1;i<=n;i++){
		vis[pref[i]]=vis[preg[i]]=true;
	}
	for(int i=1;i<=n;i++){
		for(int j=h[i];j;j=ne[j]){
			if(vis[j]==false){
				ans[j]=min(dis1[w[j]]+dis2[i]+d[j],dis1[n]);
			}
			else{
				isok[j]=true;
				add(w[j],i,d[j]);
				dijstra(1);
				h[w[j]]=ne[tot];
				tot--;
				isok[j]=false;
				ans[j]=f[n];
			}
		}
	}
	memset(vis,false,sizeof(vis));
	memset(pref,0,sizeof(pref));
	memset(preg,0,sizeof(preg));
	dijstra(n);
	dijstra1(1);
	minn+=f[1];
	for(int i=1;i<=n;i++){
		dis1[i]=f[i];dis2[i]=g[i];
	}
	for(int i=1;i<=n;i++){
		vis[pref[i]]=vis[preg[i]]=true;
	}
	for(int i=1;i<=n;i++){
		for(int j=h[i];j;j=ne[j]){
			if(vis[j]==false){
				ans[j]+=min(dis1[w[j]]+dis2[i]+d[j],dis1[1]);
			}
			else{
				isok[j]=true;
				add(w[j],i,d[j]);
				dijstra(n);
				h[w[j]]=ne[tot];
				tot--;
				isok[j]=false;
				ans[j]+=f[1];
			}
		}
	}
	for(int i=1;i<=m;i++){
		minn=min(minn,ans[i]+v[i]);
	}
	if(minn>=1e18){
		minn=-1;
	}
	printf("%lld",minn);
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}

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