Submission #118795

#	Time	Username	Problem	Language	Result	Execution time	Memory
118795		wilwxk	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	1930 ms	76152 KiB

commuter_pass

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

const int MAXN=1e5+5;
const ll INF=1e18;
set<pair<ll, int> > s;
vector<int> g[6][MAXN], pes[6][MAXN];
tuple<int, int, int> aresta[MAXN*2];
ll dist[6][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.insert({dist[k][i], i});
	while(s.size()) {
		int cur=s.begin()->second;
		s.erase(s.begin());
		for(int i=0; i<g[k][cur].size(); i++) {
			int viz=g[k][cur][i]; ll peso=pes[k][cur][i];
			if(dist[k][viz]>dist[k][cur]+peso) {
				s.erase({dist[k][viz], viz});
				dist[k][viz]=dist[k][cur]+peso;
				s.insert({dist[k][viz], viz});
			}
		}
	}
}

void liga(int a, int b, int c, int k) {
	// if(k>=2) printf("liga %d %d %d %d\n", a, b, c, k);
	g[k][a].push_back(b);
	pes[k][a].push_back(c);
}

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);
		liga(a, b, c, 0); liga(b, a, c, 0);
		liga(a, b, c, 1); liga(b, a, c, 1);
		aresta[i]={a, b, c};
	}

	dijkstra(ori, 0);
	dijkstra(dest, 1);

	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]) {
			liga(a, b, c, 2), liga(b, a, c, 2);
			liga(a, b, c, 3), liga(b, a, c, 3);
		}
		else if(dist[0][a]+c==dist[0][b]) {
			liga(a, b, 0, 2); liga(b, a, c, 2);
			liga(a, b, 0, 3); liga(b, a, c, 3);
		}
		else if(dist[0][b]+c==dist[0][a]) {
			liga(a, b, c, 2); liga(b, a, 0, 2);
			liga(a, b, c, 3); liga(b, a, 0, 3);
		}
	}

	dijkstra(x, 2);
	dijkstra(y, 3);

	// for(int i=1; i<=n; i++) printf("%d: %d %d // %d %d\n", i, dist[0][i], dist[1][i], dist[2][i], dist[3][i]);
	ll respf=min(dist[2][y], dist[3][x]);
	printf("%lld\n", respf);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[k][cur].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:36: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:37: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:38: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:40: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: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45