BZOJ 2069

bzoj_2069.cpp

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int kN = 5000+10;
const int INF = 1e9;
int N, M, first_dis[kN], last_dis[kN];
vector<PII> G[kN];

int ans = INF;
bool vis[kN];
int d[kN];
bool bit(int i, int k) {
	return i&k;
}
void Dijkstra(int k, bool inv) {
	for (int i = 1; i <= N; i++) d[i] = INF, vis[i] = false;
	priority_queue<PII> q;
	for (int i = 2; i <= N; i++) {
		if (bit(i, k)^inv) {
			q.push(PII(-first_dis[i], i));
			d[i] = first_dis[i];
		}
	}
	while (q.size()) {
		int u = q.top().second; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].first, c = G[u][i].second;
			if (d[v] > d[u]+c) {
				d[v] = d[u]+c;
				q.push(PII(-d[v], v));
			}
		}
	}
	for (int i = 2; i <= N; i++) {
		if (!(bit(i, k)^inv)) {
			ans = min(ans, d[i]+last_dis[i]);
		}
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	for (int i = 2; i <= N; i++) first_dis[i] = last_dis[i] = INF;
	for (int i = 1; i <= M; i++) {
		int u, v, c1, c2; scanf("%d %d %d %d", &u, &v, &c1, &c2);
		if (u > v) swap(u, v), swap(c1, c2);
		if (u == 1) {
			first_dis[v] = c1;
			last_dis[v] = c2;
		} else {
			G[u].push_back(PII(v, c1));
			G[v].push_back(PII(u, c2));
		}
	}
	
	for (int k = 1; k <= N; k <<= 1) {
		Dijkstra(k, false);
		Dijkstra(k, true);
	}
	
	printf("%d\n",ans);
	return 0;
}