Submission #203507

#	Time	Username	Problem	Language	Result	Execution time	Memory
203507		abacaba	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	123 ms	4604 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;

#define int long long

const long long inf=2e13;
const int N=2e2+5;
const int M=5e4+5;

int n,m,a[N];
int d[3][N][N];
int cost[M];
int curd[N],p[N];

vector<int >g[N];
vector<int >path1,path2;

priority_queue<pair<long long,long long>>q;

int is[2][M];

struct edge{
	int u,v,c,d;
	edge(){
		u=v=c=d=0;
	}
};

edge e[M];

void recover(int v,vector<int >&path){
	while(p[v]!=-1){
		path.push_back(p[v]);
		v=e[p[v]].u;
	}
	reverse(path.begin(),path.end());
}

void dxtra(int s){
	fill(curd,curd+N,inf);
	fill(p,p+N,-1);
	q.push(make_pair(0,s));
	curd[s]=0;
	while(!q.empty()){
		int d=-q.top().first,v=q.top().second;
		q.pop();
		if(d>curd[v])
			continue;
		for(int ind:g[v]){
			int to=e[ind].v,w=e[ind].c;
			if(curd[to]>curd[v]+w){
				p[to]=ind;
				curd[to]=curd[v]+w;
				q.push(make_pair(-curd[to],to));
			}
		}
	}
}

void calc_distance(){
	for(int i=0;i<3;++i)
		for(int j=0;j<N;++j)
			for(int k=0;k<N;++k)
				if(j!=k)
					d[i][j][k]=inf;

	for(int i=1;i<=m;++i)
		d[0][e[i].u][e[i].v]=min(d[0][e[i].u][e[i].v],e[i].c);
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				d[0][i][j]=min(d[0][i][j],d[0][i][k]+d[0][k][j]);

	for(int t=0;t<2;++t){
		for(int i=1;i<=m;++i)
			if(!is[t][i])
				d[t+1][e[i].u][e[i].v]=min(d[t+1][e[i].u][e[i].v],e[i].c);
		for(int k=1;k<=n;++k)
			for(int i=1;i<=n;++i)
				for(int j=1;j<=n;++j)
					d[t+1][i][j]=min(d[t+1][i][j],d[t+1][i][k]+d[t+1][k][j]);
	}
}

main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>e[i].u>>e[i].v>>e[i].c>>e[i].d;
		g[e[i].u].push_back(i);
	}

	dxtra(1);
	if(curd[n]!=inf)
		recover(n,path1);

	dxtra(n);
	if(curd[1]!=inf)
		recover(1,path2);

	for(int i=0;i<path1.size();++i)
		is[0][path1[i]]=i+1;
	for(int i=0;i<path2.size();++i)
		is[1][path2[i]]=i+1;

	calc_distance();

	for(int i=1;i<=m;++i){
		int u=e[i].u,v=e[i].v,c=e[i].c;
		if(!is[0][i])
			cost[i]+=min(d[0][1][n],d[0][1][v]+d[0][u][n]+e[i].c);
		else{
			int j=is[0][i]-1;
			int now=inf;
			for(int i=0;i<=j;++i){
				for(int k=j;k<path1.size();++k){
					int u=e[path1[i]].u,v=e[path1[k]].v;
					now=min(now,d[0][1][u]+d[1][u][v]+d[0][v][n]);
				}
			}
			cost[i]+=now;
		}
	}

	for(int i=1;i<=m;++i){
		int u=e[i].u,v=e[i].v,c=e[i].c;
		if(!is[1][i])
			cost[i]+=min(d[0][n][1],d[0][n][v]+d[0][u][1]+e[i].c);
		else{
			int j=is[1][i]-1;
			int now=inf;
			for(int i=0;i<=j;++i)
				for(int k=j;k<path2.size();++k){
					int u=e[path2[i]].u,v=e[path2[k]].v;
					now=min(now,d[0][n][u]+d[2][u][v]+d[0][v][1]);
				}
			cost[i]+=now;
		}
	}

	int ans=d[0][1][n]+d[0][n][1];

	for(int i=1;i<=m;++i)
		ans=min(ans,cost[i]+e[i].d);

	if(ans>=inf)
		cout<<-1<<endl;
	else
		cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

ho_t4.cpp:85:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path1.size();++i)
              ~^~~~~~~~~~~~~
ho_t4.cpp:102:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path2.size();++i)
              ~^~~~~~~~~~~~~
ho_t4.cpp:115:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j;k<path1.size();++k){
                 ~^~~~~~~~~~~~~
ho_t4.cpp:108:25: warning: unused variable 'c' [-Wunused-variable]
   int u=e[i].u,v=e[i].v,c=e[i].c;
                         ^
ho_t4.cpp:132:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j;k<path2.size();++k){
                 ~^~~~~~~~~~~~~
ho_t4.cpp:125:25: warning: unused variable 'c' [-Wunused-variable]
   int u=e[i].u,v=e[i].v,c=e[i].c;
                         ^

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