Submission #860201

#	Time	Username	Problem	Language	Result	Execution time	Memory
860201		pcc	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	197 ms	6888 KiB

ho_t4

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll


struct Edge{
	int to,cost,price;
	Edge(){}
	Edge(int tt,int cc,int pp){
		to = tt,cost = cc,price = pp;
	}
};

const int inf = 1e18;
const int mxn = 1e5+10;
int n,m;
bitset<mxn> del,tree,vis;
vector<int> g[220],rg[220];
int d1[220],d2[220],pid[220],d3[220],d4[220],d5[220],d6[220],d7[220],d8[220];
vector<Edge> edges;

void add_edge(int a,int b,int c,int d){
	g[a].push_back(edges.size());
	edges.push_back(Edge(b,c,d));
	rg[b].push_back(edges.size());
	edges.push_back(Edge(a,c,d));
	return;
}

void DIJKSTRA(int st,vector<int> paths[],int dist[]){
	fill(dist,dist+220,inf);
	memset(pid,-1,sizeof(pid));
	vis.reset();
	dist[st] = 0;
	int now = st;
	for(int i = 0;i<n-1;i++){
		vis[now] = true;
		for(auto eid:paths[now]){
			int nxt = edges[eid].to;
			if(del[eid])continue;
			if(dist[nxt]>dist[now]+edges[eid].cost){
				dist[nxt] = dist[now]+edges[eid].cost;
				pid[nxt] = eid;
			}
		}
		pii tmp = {inf,-1};
		for(int j = 1;j<=n;j++){
			if(vis[j])continue;
			tmp = min(tmp,make_pair(dist[j],j));
		}
		if(tmp.sc == -1)break;
		now = tmp.sc;
	}
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i = 0;i<m;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		add_edge(a,b,c,d);
	}
	DIJKSTRA(1,g,d1);
	for(int i = 1;i<=n;i++){
		if(pid[i] != -1)tree[pid[i]>>1] = true;
	}
	DIJKSTRA(n,g,d2);
	for(int i = 1;i<=n;i++){
		if(pid[i] != -1)tree[pid[i]>>1] = true;
	}
	DIJKSTRA(1,rg,d3);
	DIJKSTRA(n,rg,d4);
	ll ans = inf;
	ans = min(ans,d1[n]+d2[1]);
	/*
	cout<<"d1:";for(int i = 1;i<=n;i++)cout<<d1[i]<<' ';cout<<endl;
	cout<<"d2:";for(int i = 1;i<=n;i++)cout<<d2[i]<<' ';cout<<endl;
	cout<<"d3:";for(int i = 1;i<=n;i++)cout<<d3[i]<<' ';cout<<endl;
	cout<<"d4:";for(int i = 1;i<=n;i++)cout<<d4[i]<<' ';cout<<endl;

   */

	for(int i = 0;i<edges.size();i+=2){
		if(tree[i>>1]){
			del[i] = del[i^1] = true;
			add_edge(edges[i].to,edges[i^1].to,edges[i].cost,edges[i].price);
			DIJKSTRA(1,g,d5);
			DIJKSTRA(n,g,d6);
			g[edges[i].to].pop_back();
			rg[edges[i^1].to].pop_back();
			edges.pop_back();edges.pop_back();
			del[i] = del[i^1] = false;
			ans = min(ans,d5[n]+d6[1]+edges[i].price);
			//cout<<i<<":"<<edges[i^1].to<<' '<<edges[i].to<<":"<<d5[n]<<' '<<d6[1]<<' '<<edges[i].price<<endl;
		}
		else{
			int tans = min(d1[edges[i].to]+d4[edges[i^1].to]+edges[i].cost,d1[n]);
			tans += min(d2[edges[i].to]+d3[edges[i^1].to]+edges[i].cost,d2[1]);
			tans += edges[i].price;
			ans = min(ans,tans);
		}
	}
	cout<<(ans>=inf?-1:ans);
}

Compilation message (stderr)

ho_t4.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main(){
      | ^~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:92:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0;i<edges.size();i+=2){
      |                ~^~~~~~~~~~~~~

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