首页 > 代码库 > NYIST 1019 G.亲戚来了
NYIST 1019 G.亲戚来了
G.亲戚来了
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
Bob 一家人要去下馆子，为什么呢？因为他姑姑的大爷的叔叔的孙子的表叔的婶婶的儿子来了，亲戚来了当然要下馆子，可是Bob家在偏僻的小山屯，饭店在城里啊
距离老远了。。。。。
于是他们决定坐车去，可是家里面就有一辆车啊，还是个拖拉机。。。。。。
并且，山路不好走啊，不能过超过这条路的载客量，于是不得不再回去一趟。。。。。。
比如，在下面的地图，假设Bob家在1号村庄，饭店在7号村庄，其中一条边表示给条路上的最大载客量
现在Bob要将他的亲戚以及家人99人(不包含Bob)送到城里面，选择的最好路线是1->2->4->7
并且往返5次。。。。。现在我们请你帮忙计算Bob将亲戚以及家人送到城镇里面所用的最少往返次数。。。
- 输入
- 输入包含若干组数据，每组数据的第一行有两个整数n(n<=100)和r，分别表示村庄的数量，和道路的数量，接下来的R行每行有三个整数
u,v,w;表示u号村庄到v号村庄有一条路以及这条路的最大载客量为w，
随后的一行三个数x,y,d，表示Bob的家在x号村庄，饭店在y号村庄以及Bob和他亲戚的总人数 - 输出
- 输出最少的往返的次数，如果到达不了请输出-1；
- 样例输入
7 101 2 301 3 151 4 102 4 252 5 603 4 403 6 204 7 355 7 206 7 301 7 99
- 样例输出
5
- 上传者
- ACM_王亚龙
解题：试了几种姿势，发现求最短路比较好，不过要注意起点等于终点这种坑爹情况。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 110;18 struct arc{19 int to,w,next;20 arc(int x = 0,int y = 0,int z = -1){21 to = x;22 w = y;23 next = z;24 }25 };26 arc e[maxn*maxn];27 int head[maxn],tot,n,m,S,T,d[maxn];28 bool done[maxn];29 void add(int u,int v,int cost){30 e[tot] = arc(v,cost,head[u]);31 head[u] = tot++;32 }33 void dijkstra(){34 for(int i = 1; i <= n; ++i){35 d[i] = 0;36 done[i] = false;37 }38 priority_queue< pii,vector< pii >,less< pii > >q;39 d[S] = INF;40 q.push(make_pair(d[S],S));41 while(!q.empty()){42 int u = q.top().second;43 q.pop();44 if(done[u]) continue;45 done[u] = true;46 for(int i = head[u]; ~i; i = e[i].next){47 if(d[e[i].to] < min(d[u],e[i].w)){48 d[e[i].to] = min(d[u],e[i].w);49 q.push(make_pair(d[e[i].to],e[i].to));50 }51 }52 }53 }54 int main(){55 int u,v,w;56 while(~scanf("%d %d",&n,&m)){57 memset(head,-1,sizeof(head));58 for(int i = tot = 0; i < m; ++i){59 scanf("%d %d %d",&u,&v,&w);60 add(u,v,w);61 add(v,u,w);62 }63 scanf("%d %d %d",&S,&T,&w);64 if(S == T){65 puts("0");66 continue;67 }68 dijkstra();69 if(d[T] <= 1) puts("-1");70 else{71 double tmp = w*1.0/(d[T]-1);72 printf("%.0f\n",ceil(tmp));73 }74 }75 return 0;76 }
NYIST 1019 G.亲戚来了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。