Submission #118800

#	Time	Username	Problem	Language	Result	Execution time	Memory
118800		wilwxk	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	855 ms	40796 KiB

commuter_pass

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

const int MAXN=1e5+5;
const ll INF=1e18;
vector<int> g[MAXN], pes[MAXN];
vector<int> dg[5][MAXN];
priority_queue<pair<ll, int> > s;
tuple<int, int, int> aresta[MAXN*2];
ll dist[5][MAXN], dp[2][MAXN];
int gin[2][MAXN];
short marc[MAXN];
int n, m, ori, dest, x, y;

void dijkstra(int ori, int k) {
	for(int i=1; i<=n; i++) dist[k][i]= i==ori ? 0 : INF, s.push({-dist[k][i], i});
	memset(marc, 0, sizeof(marc));
	while(s.size()) {
		int cur=s.top().second; s.pop();
		if(marc[cur]) continue; marc[cur]=1;
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; ll peso=pes[cur][i];
			if(dist[k][viz]>dist[k][cur]+peso) {
				dist[k][viz]=dist[k][cur]+peso;
				s.push({-dist[k][viz], viz});
			}
		}
	}
}

void bfs(int k) {
	queue<int> qu;
	for(int i=1; i<=n; i++) if(gin[k][i]==0) qu.push(i);
	while(qu.size()) {
		int cur=qu.front(); qu.pop();
		for(auto viz : dg[k][cur]) {
			gin[k][viz]--;
			if(gin[k][viz]==0) qu.push(viz);
			dp[k][viz]=min(dp[k][viz], dp[k][cur]);
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	scanf("%d %d", &ori, &dest);
	scanf("%d %d", &x, &y);
	for(int i=1; i<=m; i++) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		aresta[i]={a, b, c};
		g[a].push_back(b); g[b].push_back(a);
		pes[a].push_back(c); pes[b].push_back(c);
	}
	dijkstra(ori, 0); dijkstra(dest, 1);
	dijkstra(x, 2); dijkstra(y, 3);
	for(int i=1; i<=n; i++) dp[0][i]=dp[1][i]=dist[2][i];

	for(int i=1; i<=m; i++) {
		int a, b, c; tie(a, b, c)=aresta[i];
		if(dist[0][a]+dist[1][b]+c!=dist[0][dest]&&dist[0][b]+dist[1][a]+c!=dist[0][dest]) continue;
		if(dist[0][a]+c==dist[0][b]) {
			dg[0][a].push_back(b); gin[0][b]++;
			dg[1][b].push_back(a); gin[1][a]++;
		}
		if(dist[0][b]+c==dist[0][a]) {
			dg[0][b].push_back(a); gin[0][a]++;
			dg[1][a].push_back(b); gin[1][b]++;
		}
	}

	bfs(0); bfs(1);
	// for(int i=1; i<=n; i++) printf("%d: %lld %lld // %lld %lld\n", i, dist[0][i], dist[1][i], dist[2][i], dist[3][i]);
	// for(int i=1; i<=n; i++) printf("dp[%d]= (%lld ; %lld)\n", i, dp[0][i], dp[1][i]);

	ll respf=INF;
	for(int i=1; i<=n; i++) respf=min(respf, dist[3][i]+min(dp[0][i], dp[1][i]));

	printf("%lld\n", respf);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:21:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(marc[cur]) continue; marc[cur]=1;
   ^~
commuter_pass.cpp:21:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(marc[cur]) continue; marc[cur]=1;
                           ^~~~
commuter_pass.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &ori, &dest);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:50:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45