Instantly share code, notes, and snippets.

@Chenyao2333 Chenyao2333/bzoj_2069.cpp
Last active Aug 29, 2015

Embed
What would you like to do?
BZOJ 2069
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment