Problem B: 周末出游计划
Time Limit: 4 Sec Memory Limit:
128 MB
Submit: 333 Solved: 38
[Submit][Status][Web
Board]
Description
邻近周末,小Q想出去走走,去见见世面。由于某猫搞双十二,整个社会都乱了,包括市区的公共交通系统。为了庆祝双十二,所以单身男子可以在一个星期内享受一种非常神奇的优惠乘车方案,当然这个周末也在优惠期内。小Q呢,作为一个精打细算的优质单身男士(咳咳),有这种便利当然要用一用了。
乘车规则如下:
1. 任意路线的相邻两站都有一个乘车费用。公交线路都是有往返的,而且价格相同。
2. 如果一个单身男子从A站来到B站,那么他只需要支付AB站间的费用与他从起点来到A站之间总共花费的差值,如果差值为负,那么本段路线完全免费。
已知整个城市里一共有N个站点,我们将它们编号为1到N,出游起点为1号站点,终点为N号站点。我们都知道小Q喜欢精打细算(其实修篱笆的时候大家都知道了~~),他希望趁着双十二的福利,找到一种从1号点到N号点的最廉价乘车路线方案。
Input
多组测试数据。
对于每组数据:
第1行:两个整数N和M分别代表站点数和路线的数量(1 <= N <= 20,000, 1 <= M <= 200,000)。
第2到M+1行:每行输入三个整数x, y, w(1 <= x, y <= N, 1 <= w <= 10,000,000)分别代表x号站点和y号站点之间有一条路线,需要花费w元钱。
Output
对于每组数据,输出一行,包含一个整数,代表最便宜的乘车路线的价格。如果小Q无法到达目的地,请输出-1。
Sample Input
5 51 2 603 5 70 1 4 1204 5 1502 3 80
Sample Output
80
HINT
模型很容易看出来,就是求一条路径上的最大边权最小。所以二分边权,大于该边权的边去掉。然后判断1和n是否在同一个集合中,我的BFS能过,但是最好还是用并查集。
要去边操作,并且很稀疏,因此用前向星。
#include <cstdio> #include <string> #include <cstring> #include <algorithm> using std::sort; const int maxm = 200010; const int maxn = 20010; struct EDGE { int u,v,w; bool operator<(const EDGE& e2)const { return u < e2.u; } }edge[maxm*2]; int W[maxm]; bool rem[maxm*2]; inline int getint() { int res=0;char tmp;bool sgn=1; do tmp=getchar(); while (!isdigit(tmp)&&tmp!='-'); if (tmp=='-'){sgn=0;tmp=getchar();} do res=(res<<3)+(res<<1)+tmp-'0'; while (isdigit(tmp=getchar())); return sgn?res:-res; } bool used[maxn]; int start[maxn]; const int qmod = 5000000; int que[qmod + 10]; int m,n; void remove(int vv) { for (int i=1;i<=m;i++) if (edge[i].w > vv) rem[i] = true; } bool can() { int l = 0; int r = 0; que[++r] = 1; memset(used,0,sizeof used); used[1] = true; while (l != r) { l ++;if (l==qmod) l=0; int u = que[l]; if (u == n) return true; for (int vv=start[u];edge[vv].u == u;vv++) { if (rem[vv]) continue; int v = edge[vv].v; if (!used[v]) { used[v] = true; r ++;if (r==qmod) r = 0; que[r] = v; } } } return false; } int bin() { int rs = 0x3f3f3f3f; int l = 1; int r = m/2; while (l <= r) { int mid = (l+r)/2; memset(rem,0,sizeof rem); remove(W[mid]); if (can()) { r = mid - 1; if (rs > W[mid]) rs = W[mid]; } else l = mid + 1; } return rs; } int main() { bool first = true; while (scanf("%d%d",&n,&m)==2) { if (!first) printf("\n"); first = false; memset(start,0,sizeof start); int cnt = 0; for (int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); ++cnt; edge[cnt].u = u; edge[cnt].v = v; edge[cnt].w = w; ++cnt; edge[cnt].u = v; edge[cnt].v = u; edge[cnt].w = w; W[i] = w; } m = cnt; sort(W+1,W+1+m/2); sort(edge+1,edge+1+m); for (int i=1;i<=m;i++) if (!start[edge[i].u]) start[edge[i].u] = i; memset(rem,0,sizeof rem); if (!can()) printf("-1"); else { int ans = bin(); printf("%d",ans); } } return 0; }