제출 #287194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287194		arnold518	Olympic Bus (JOI20_ho_t4)	C++14	11 / 100	150 ms	8568 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 = 1e18;

struct Edge
{
	int u, v; ll c, d; int p;
	bool operator < (const Edge &q) const { return p<q.p; }
};

int N, M;
vector<Edge> adj[MAXN+10], radj[MAXN+10];
Edge E[MAXM+10];
ll ans[MAXM+10];

ll DA[MAXN+10], DB[MAXN+10], RDA[MAXN+10], RDB[MAXN+10];
int PA[MAXN+10], PB[MAXN+10], RPA[MAXN+10], RPB[MAXN+10];

ll TD[MAXN+10];
int TP[MAXN+10];

bool vis[MAXN+10];

void dijk(vector<Edge> *G, int S, ll *D, int *P)
{
	for(int i=1; i<=N; i++) D[i]=INF, P[i]=-1, vis[i]=0;
	D[S]=0;

	while(1)
	{
		int now=-1; ll val=INF;
		for(int i=1; i<=N; i++)
		{
			if(vis[i]) continue;
			if(val>D[i]) val=D[i], now=i;
		}
		if(now==-1) break;
		vis[now]=1;
		//printf("!%d %lld\n", now, val);

		for(auto nxt : G[now])
		{
			if(vis[nxt.v]) continue;
			if(val+nxt.c<=D[nxt.v])
			{
				D[nxt.v]=val+nxt.c;
				P[nxt.v]=now;
			}
		}
	}
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int 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});
		E[i]={u, v, c, d, i};
	}
	for(int i=1; i<=N; i++) sort(adj[i].begin(), adj[i].end());

	dijk(adj, 1, DA, PA);
	dijk(adj, N, DB, PB);
	dijk(radj, 1, RDA, RPA);
	dijk(radj, N, RDB, RPB);

	{
		vector<int> V;
		for(int i=1; i<=N; i++) if(PA[i]) V.push_back(PA[i]);
		for(int i=1; i<=N; i++) if(RPB[i]) V.push_back(RPB[i]);

		sort(V.begin(), V.end());

		for(int i=1; i<=M; i++)
		{
			if(binary_search(V.begin(), V.end(), i))
			{
				auto it=lower_bound(adj[E[i].u].begin(), adj[E[i].u].end(), E[i]);
				it->c=INF;
				dijk(adj, 1, TD, TP);
				ans[i]+=TD[N];
				it->c=E[i].c;
			}
			else
			{
				ans[i]+=min(DA[E[i].v]+E[i].c+RDB[E[i].u], DA[N]);
			}
		}
	}

	{
		vector<int> V;
		for(int i=1; i<=N; i++) if(PB[i]) V.push_back(PB[i]);
		for(int i=1; i<=N; i++) if(RPA[i]) V.push_back(RPA[i]);

		sort(V.begin(), V.end());

		for(int i=1; i<=M; i++)
		{
			if(binary_search(V.begin(), V.end(), i))
			{
				auto it=lower_bound(adj[E[i].u].begin(), adj[E[i].u].end(), E[i]);
				it->c=INF;
				dijk(adj, N, TD, TP);
				ans[i]+=TD[1];
				it->c=E[i].c;
			}
			else
			{
				ans[i]+=min(DB[E[i].v]+E[i].c+RDA[E[i].u], DB[1]);
			}
		}
	}
	for(int i=1; i<=M; i++) ans[i]+=E[i].d;

	ll val=DA[N]+DB[1];
	for(int i=1; i<=M; i++) val=min(val, ans[i]);
	if(val>=INF) val=-1;
	printf("%lld\n", val);
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |   scanf("%d%d%d%d", &u, &v, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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