Submission #206000

#	Time	Username	Problem	Language	Result	Execution time	Memory
206000		arnold518	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	323 ms	9848 KiB

ho_t4

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 200;
const int MAXM = 5e4;
const ll INF = 1e17;

struct Edge
{
	int u, v; ll c, d; int p;
};

struct Queue
{
	int u; ll w;
	bool operator < (const Queue &p) const { return w>p.w; }
};

int N, M;
Edge edge[MAXM+10];
vector<Edge> adj[MAXN+10], radj[MAXN+10], tadj[MAXN+10];
ll D1[MAXN+10], D2[MAXN+10], RD1[MAXN+10], RD2[MAXN+10], DT[MAXN+10];

ll val[MAXM+10], ans;
bool chk[MAXN+10], tree[MAXM+10];

void dijk(int s, vector<Edge> *adj, ll *D)
{
	int i, j;

	priority_queue<Queue> PQ;
	for(i=1; i<=N; i++) D[i]=INF;
	PQ.push({s, 0}); D[s]=0;
	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(D[now.u]<now.w) continue;
		for(auto nxt : adj[now.u]) if(D[nxt.v]>now.w+nxt.c) D[nxt.v]=now.w+nxt.c, PQ.push({nxt.v, now.w+nxt.c});
	}
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++)
	{
		int u, v, c, d;
		scanf("%d%d%d%d", &u, &v, &c, &d);
		adj[u].push_back({u, v, c, d, i});
		radj[v].push_back({v, u, c, d, i});
		edge[i]={u, v, c, d, i};
		val[i]=d;
	}

	dijk(1, adj, D1);
	dijk(N, adj, D2);
	dijk(1, radj, RD1);
	dijk(N, radj, RD2);

	memset(chk, 0, sizeof(chk));
	memset(tree, 0, sizeof(tree));
	for(i=1; i<=N; i++) for(auto nxt : adj[i])
	{
		if(D1[nxt.u]!=INF && D1[nxt.v]!=INF && D1[nxt.u]+nxt.c==D1[nxt.v] && !chk[nxt.v])
		{
			chk[nxt.v]=1;
			tree[nxt.p]=1;
		}
	}

	val[0]+=D1[N];
	for(i=1; i<=M; i++)
	{
		if(tree[i])
		{	
			for(j=1; j<=N; j++) tadj[j].clear();
			for(j=1; j<=M; j++)
			{
				if(j!=i) tadj[edge[j].u].push_back({edge[j].u, edge[j].v, edge[j].c, edge[j].d, edge[j].p});
				else tadj[edge[j].v].push_back({edge[j].v, edge[j].u, edge[j].c, edge[j].d, edge[j].p});
			}
			dijk(1, tadj, DT);
			val[i]+=DT[N];
		}
		else
		{
			val[i]+=min(D1[N], D1[edge[i].v]+RD2[edge[i].u]+edge[i].c);
		}
	}

	memset(chk, 0, sizeof(chk));
	memset(tree, 0, sizeof(tree));
	for(i=1; i<=N; i++) for(auto nxt : adj[i])
	{
		if(D2[nxt.u]!=INF && D2[nxt.v]!=INF && D2[nxt.u]+nxt.c==D2[nxt.v] && !chk[nxt.v])
		{
			chk[nxt.v]=1;
			tree[nxt.p]=1;
		}
	}

	val[0]+=D2[1];
	for(i=1; i<=M; i++)
	{
		if(tree[i])
		{	
			for(j=1; j<=N; j++) tadj[j].clear();
			for(j=1; j<=M; j++)
			{
				if(j!=i) tadj[edge[j].u].push_back({edge[j].u, edge[j].v, edge[j].c, edge[j].d, edge[j].p});
				else tadj[edge[j].v].push_back({edge[j].v, edge[j].u, edge[j].c, edge[j].d, edge[j].p});
			}
			dijk(N, tadj, DT);
			val[i]+=DT[1];
		}
		else
		{
			val[i]+=min(D2[1], D2[edge[i].v]+RD1[edge[i].u]+edge[i].c);
		}
	}
	printf("!%lld %lld\n", D1[N], D2[1]);

	ans=INF;
	for(i=0; i<=M; i++) ans=min(ans, val[i]);
	for(i=0; i<=M; i++) if(val[i]<INF) printf("%d : %lld\n", i, val[i]);
	if(ans>=INF) ans=-1;
	printf("%lld", ans);
}

Compilation message (stderr)

ho_t4.cpp: In function 'void dijk(int, std::vector<Edge>*, ll*)':
ho_t4.cpp:33:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &u, &v, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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