L3-005 垃圾箱分布（dijkstra）

本文主要是介绍L3-005 垃圾箱分布（dijkstra），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

拿起题就开始写，最后提交测试点2和测试点3就是过不去。
感觉一点问题都没有，好郁闷，找了半天，发现地点的编号是0开始的，而我一直在从1遍历....
思路就是两个dijkstra，这两次思路是完全一样的，只是一个是最短距离最少节点，一个是最短时间最短距离，所以分别需要增加一个累计经过节点数量和累计节点距离（cnt和distances）。
结果我都是用dist来存的，第一个dist表示的是最短路径，第二个表示的是最短时间。

代码:

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int distances[1010][1010];
int dis[1020],visited[1020];
int edges[1020][1020]; 
void dijkstra(int dis[],int visited[],int n,int s){//s起点 dis[s]=0;for(int i=1;i<=n;i++){int minv = inf,minx;for(int j=1;j<=n;j++){if(!visited[j]&&dis[j]<minv){minv=dis[j];minx=j;}}visited[minx]=1;for(int j=1;j<=n;j++){if(minv+edges[minx][j]<dis[j]){dis[j]=minv+edges[minx][j];}}}
}
int main(){memset(edges,0x3f,sizeof(edges));int n,m,k,ds;cin>>n>>m>>k>>ds;//居民点的个数 垃圾箱的个数 路径条数 最远不能超过 char s1[10],s2[10];int dist;for(int i=1;i<=k;i++){//输入 cin>>s1>>s2>>dist;int x = s1[0]=='G'?atoi(s1+1)+n:atoi(s1);int y = s2[0]=='G'?atoi(s2+1)+n:atoi(s2);edges[x][y]=edges[y][x]=dist;} for(int i=1;i<=m;i++){memset(visited,0,sizeof(visited));memset(dis,0x3f,sizeof(dis));dijkstra(dis,visited,n+m,n+i);for(int j=1;j<=n;j++){distances[i][j]=dis[j];}}vector<int> res;int mins=0,path=inf; //到所有的居民点的最短距离中最长的那个for(int i=1;i<=m;i++){//第i个垃圾箱 int cmins=inf,cpath=0;int flag = 1;for(int j=1;j<=n;j++){if(distances[i][j]>ds){//这个垃圾桶不行 flag = 0;break;}cpath=cpath+distances[i][j];//更新最短距离cmins = min(distances[i][j],cmins); }if(!flag) continue;if(cmins>mins){//更长 mins=cmins;//更新 path=cpath; res.clear();res.push_back(i);}else if(cmins==mins){//平均距离if(cpath<path) {res.clear();res.push_back(i);path=cpath;//更新 }}}if(res.size()==0){cout << "No Solution" << '\n';}else{cout << "G" << *res.begin() << '\n';printf("%.1f %.1f",(double)mins,(double)path/n);}return 0;
}

这篇关于L3-005 垃圾箱分布（dijkstra）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---