首页 > 代码库 > 赶赴王都[暴力骗分的做法]
赶赴王都[暴力骗分的做法]
在利贝尔王国王都格兰赛尔正处于一场危机当中，获得消息的小约和小艾正打算赶赴那里，阻止这场阴谋。但是在出发前，他们发生了分歧，小艾希望走最短路，以尽快到达王都，而小约则希望多走不同的道路，以收集情报。后来，他们想到了折衷的办法，选一条路径，使得总路程除以道路数的商最小（即边权平均值最小）。
输入：给出利贝尔王国的地图。
第一行为两个整数n，m。表示共n个地点，其中1为小约和小艾的出发点，n为王都。另有m条道路连接这些地点。
接下来m行，每行3个整数x，y，z，描述一条有向道路。表示x到y有一条长度为z的道路。数据保证，不会出现环，且至少有一条从1到n的路。但两个地点之间可能有多条道路。
输出：只有一个实数，即最小边权平均值。答案保留两位小数。
样例输入：4 6
1 2 1
2 4 6
1 3 2
3 4 4
2 3 3
1 4 8
样例输出：2.67
数据范围：30% 的数据1<=n<=20，1<=m<=20
100%的数据1<=n<=10^3,，1<=m<=20000 ，其余数据在[0,10^3]。
据40大神说是01分数规划= = 人弱不会> <
但是，学习了一下这题的暴力做法，觉得还是有启发的；
dist[i][j]表示的从1~i,走过j条边的最小值；
vis[i][j]类推；
还是一遍spfa，但是因为dist是二维的，还记录了走过了多少条边，需要转移边的个数，所以写起来也有小小的区别；
首先queue,因为你入队的有第几个结点，和走过多少条边，所以queue 定义为node
之后同理，松弛操作的时候 多一个转移边的个数即可；
具体的看程序：
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const int maxn=1001,maxm=20001;int dist[maxn][maxm],vis[maxn][maxm];int n,m;struct edge{ int to,w; edge(int _to,int _w){to=_to;w=_w;}};vector <edge> g[maxm];int x,y,z;double minx=1234567844.0;struct node{ int x,num; node(int _x,int _num){x=_x;num=_num;}};queue <node> q;void spfa(int x){ memset(dist,63,sizeof(dist)); dist[1][0]=0; vis[1][0]=1; q.push(node(1,0)); while(!q.empty()){ node temp=q.front();//注意这里； q.pop(); int u=temp.x; vis[u][temp.num]=0; int l=g[u].size(); for(int i=0;i<l;i++){ int v=g[u][i].to; if(dist[v][temp.num+1]>dist[u][temp.num]+g[u][i].w){ dist[v][temp.num+1]=dist[u][temp.num]+g[u][i].w; if(!vis[v][temp.num+1]){ q.push(node(v,temp.num+1)); } } } }}int main(){ freopen("troops.in","r",stdin); freopen("troops.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); g[x].push_back(edge(y,z)); } spfa(1); for(int i=1;i<=m;i++){ double ans=dist[n][i]/(i+0.0); if(ans<minx) minx=ans; } printf("%.2f",minx); return 0;}
赶赴王都[暴力骗分的做法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。