首页 > 代码库 > 505. 城市（二分答案）
505. 城市（二分答案）
505. 城市
★★ 输入文件：cost.in 输出文件：cost.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
在某个遥远的国家里，有n个城市。编号为1，2，3，……，n。
这个国家的政府修建了m条双向的公路。每条公路连接着两个城市。沿着某条公路，开车从一个城市到另一个城市，需要花费一定的汽油。
开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有的收费站都在城市中，在城市间的公路上没有任何的收费站。
小红现在要开车从城市u到城市v(1<=u，v<=n)。她的车最多可以装下s升的汽油。在出发的时候，车的油箱是满的，并且她在路上不想加油。
在路上，每经过一个城市，她要交一定的费用。如果她某次交的费用比较多，她的心情就会变得很糟。所以她想知道，在她能到达目的地的前提下，她交的费用中最多的一次最少是多少。这个问题对于她来说太难了，于是她找到了聪明的你，你能帮帮她吗？
【输入格式】
第一行5个正整数，n，m，u，v，s。分别表示有n个城市，m条公路，从城市u到城市v，车的油箱的容量为s升。
接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。
再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，需要用ci升汽油。
【输出格式】
仅一个整数，表示小红交费最多的一次的最小值。
如果她无法到达城市v，输出-1。
【输入样例1】
4 4 2 3 8856102 1 22 4 11 3 43 4 3
- 【输出样例1】
8
- 【输入样例2】
4 4 2 3 3856102 1 22 4 11 3 43 4 3
- 【输出样例2】
-1
- 【数据规模】
对于60%的数据，满足n<=200，m<=10000，s<=200
对于100%的数据，满足n<=10000，m<=50000，s<=1000000000
对于100%的数据，满足ci<=1000000000，fi<=1000000000，可能有两条边连接着相同的城市。
dijkstra，二分答案。堆优化
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 const int MAXN = 10100 ; 7 struct Edge{ 8 int to,w,nxt; 9 }e[100010];10 struct Node{11 int node,dist;12 bool operator < (const Node& a) const13 {14 return dist > a.dist;15 }16 }k;17 int c[MAXN],head[MAXN],dis[MAXN];18 bool vis[MAXN];19 int st,en,s,cnt,n,m;20 priority_queue<Node>q;21 void add(int u,int v,int w)22 {23 ++cnt;24 e[cnt].to = v;25 e[cnt].w = w;26 e[cnt].nxt = head[u];27 head[u] = cnt; 28 } 29 bool ok(int x)30 {31 if (c[st]>x||c[en]>x) return false;32 memset(dis,0x3f,sizeof(dis));33 memset(vis,false,sizeof(vis));34 dis[st] = 0;35 vis[st] = true;36 q.push((Node){st,dis[st]});37 while (!q.empty())38 {39 k = q.top();40 q.pop();41 int u = k.node;42 vis[u] = false;43 for (int i=head[u]; i; i=e[i].nxt)44 {45 int v = e[i].to, w = e[i].w;46 if (c[v]>x) continue ;47 if (dis[v]>dis[u]+w)48 {49 dis[v] = dis[u]+w;50 if (!vis[v])51 {52 q.push((Node){v,dis[v]});53 vis[v] = true;54 }55 }56 }57 }58 if (dis[en] > s) return false ;59 return true ;60 }61 int main()62 {63 freopen("cost.in","r",stdin);64 freopen("cost.out","w",stdout);65 int l=1e9,r=0;66 scanf("%d%d%d%d%d",&n,&m,&st,&en,&s);67 for (int i=1; i<=n; ++i)68 {69 scanf("%d",&c[i]);70 r = max(c[i],r);71 l = min(c[i],l); 72 }73 for (int x,y,z,i=1; i<=m; ++i)74 {75 scanf("%d%d%d",&x,&y,&z);76 add(x,y,z);77 add(y,x,z);78 }79 if (!ok(r))80 {81 printf("-1");82 return 0;83 }84 while (l<=r)85 {86 int mid = (l+r)>>1;87 if (ok(mid)) r = mid-1;88 else l = mid+1;89 }90 printf("%d",r+1);91 return 0;92 }
70分spfa代码，首先想的是spfa，单3个点超时
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 const int MAXN = 10100 ; 7 struct Edge{ 8 int to,w,nxt; 9 }e[50010];10 int c[MAXN],head[MAXN],dis[MAXN];11 bool vis[MAXN];12 int st,en,s,cnt,n,m;13 14 void add(int u,int v,int w)15 {16 ++cnt;17 e[cnt].to = v;18 e[cnt].w = w;19 e[cnt].nxt = head[u];20 head[u] = cnt; 21 } 22 bool ok(int x)23 {24 if (c[st]>x) return false;25 memset(dis,0x3f,sizeof(dis));26 memset(vis,0,sizeof(vis));27 queue<int>q;28 q.push(st);29 dis[st] = 0;30 vis[st] = true;31 while (!q.empty())32 {33 int u = q.front();34 q.pop();35 for (int i=head[u]; i; i=e[i].nxt)36 {37 int v = e[i].to;38 int w = e[i].w;39 if (c[v]>x) continue ;40 if (dis[v]>dis[u]+w)41 {42 dis[v] = dis[u]+w;43 if (!vis[v])44 {45 q.push(v);46 vis[v] = true;47 }48 }49 }50 vis[u] = false;51 }52 if (dis[en] > s) return false ;53 return true ;54 }55 int main()56 {57 freopen("cost.in","r",stdin);58 freopen("cost.out","w",stdout);59 int l=1e9,r;60 scanf("%d%d%d%d%d",&n,&m,&st,&en,&s);61 for (int i=1; i<=n; ++i)62 {63 scanf("%d",&c[i]);64 r = max(c[i],r);65 l = min(c[i],l); 66 }67 for (int x,y,z,i=1; i<=m; ++i)68 {69 scanf("%d%d%d",&x,&y,&z);70 add(x,y,z);71 add(y,x,z);72 }73 if (!ok(r))74 {75 printf("-1");76 return 0;77 }78 while (l<=r)79 {80 int mid = (l+r)>>1;81 if (ok(mid)) r = mid-1;82 else l = mid+1;83 }84 printf("%d",r+1);85 return 0;86 }
505. 城市（二分答案）