1072. Gas Station (30)-PAT甲级真题(Dijkstra)

 

原题:https://www.patest.cn/contests/pat-a-practise/1072

每次遍历d[],求所有最短路径中最小的;

#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
using namespace std;
const int maxn = 1011, INF = 1000000000;
int n, m, k, ds, g[maxn][maxn], d[maxn], vis[maxn];

int string2int(string str) {
	stringstream ss;
	int a;
	ss << str;
	ss >> a;
	return a;
}
int dijkstra(int v, int &minds, int &add) {
	int min, u;
	fill(vis, vis + maxn, 0);
	fill(d, d + maxn, INF);
	d[v] = 0;
	for (int i = 0; i < n + m; i++) {
		min = INF;
		for (int j = 1; j <= n + m; j++) {
			if (vis[j] == 0 && min > d[j]) {
				min = d[j];
				u = j;
			}
		}
		vis[u] = 1;
		for (int k = 1; k <= n + m; k++) {
			if (vis[k] == 0 && d[k] > d[u] + g[u][k])
				d[k] = d[u] + g[u][k];
		}
	}
for(int i=1;i<=n;i++)/*遍历d[],不能在求d[]的过程中遍历,只能全部求完d[]之后
 {
 if(d[i]>ds)
 return 1;
 add+=d[i];
 if(minds>d[i])
 minds=d[i];
 }
 return -1;
 }
 int main()
 {
 int id1,id2;
 int ansid,ansds=0,ansadd=INF,minds,add;
 cin>>n>>m>>k>>ds;
 fill(g[0],g[0]+maxn*maxn,INF);
 string a,b;
 for(int i=0;i<k;i++)
 {
 cin>>a>>b;
 if(a[0]=='G')
 id1=n+string2int(a.substr(1));
 else
 id1=string2int(a);
 if(b[0]=='G')
 id2=n+string2int(b.substr(1,b.size()-1));
 else
 id2=string2int(b);
 cin>>g[id1][id2];
 g[id2][id1]=g[id1][id2];
 }
 for(int i=1;i<=m;i++)
 {
 minds=INF;
 add=0;
 if(dijkstra(n+i,minds,add)>0)
 continue;
 if(minds>ansds)
 {
 ansds=minds;
 ansid=n+i;
 ansadd=add;
 }
 else if(minds==ansds&&add<ansadd)
 {
 ansid=n+i;
 ansadd=add;
 }
 }
 if(ansadd==INF)
 cout<<"No Solution"<<endl;
 else
 {
 cout<<"G"<<ansid-n<<endl;
 printf("%0.1f %0.1f\n",ansds*1.0,ansadd*1.0/n);
 }
 return 0;
 }

 

0

发表评论

邮箱地址不会被公开。 必填项已用*标注