A1072 Gas Station (30 分)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int inf = 1000000;
const int maxn = 1100;
int N, M, K, Ds;
int cost[maxn][maxn]; 
int used[maxn], d[maxn]; 
void init(){
	fill(cost[0], cost[0] + maxn * maxn, inf);	
}
void dijkstra(int s){
	memset(used, 0, sizeof(used));
	fill(d, d + maxn, inf);	
	d[s] = 0;
	for(int i = 1; i <= N + M; i++){
		int u = -1, Min = inf; 
		for(int v = 1; v <= N + M; v++){
			if(used[v] == 0 && d[v] < Min){
				Min = d[v]; u = v;
			}
		}
		if(u == -1) break;
		used[u] = 1;				
		for(int v = 1; v <= N + M; v++){
			if(used[v] == 0 && cost[u][v] != inf){
				d[v] = min(d[v], d[u] + cost[u][v]);				
			}
		}	
	}	
}
void solve(){
	int noG;
	double minTotal = inf, maxDis = -1;
	for(int i = N+1; i <= N+M; i++){
		dijkstra(i);
		double total = 0, tempDis = inf;
		for(int j = 1; j <= N; j++){
			if(d[j] > Ds){
				total = -1; break;
			}
			total += 1.0*d[j];
			tempDis = min(tempDis, 1.0*d[j]);
		}		
		if(total < 0) continue;
		if(tempDis > maxDis || (tempDis == maxDis && total < minTotal)){
			maxDis = tempDis;
			minTotal = total;
			noG = i - N;
		}		
	}
	if(minTotal == inf) printf("No Solution\n");
	else{	
		printf("G%d\n", noG);
		printf("%.1f %.1f\n", maxDis, (minTotal+0.01)/N);
	}
}
int str2num(string str){
	int num = 0, add = 0, i = 0;
	if(str[0] == 'G'){
		i = 1;;
		add = N;
	}
	for(; i < str.size(); i++){
		num = num * 10 + str[i] - '0';
	}
	return num + add;
}
int main(){
	init();
	scanf("%d %d %d %d", &N, &M, &K, &Ds);
	string s1, s2; 
	int x, y, w;	
	for(int i = 0; i < K; i++){
		cin >> s1 >> s2 >> w;
		x = str2num(s1);
		y = str2num(s2);
		cost[x][y] = cost[y][x] = w;
	}
	solve();
	return 0;
}

 

上一篇:[LeetCode] 134. Gas Station


下一篇:百度Apollo5.0控制模块代码学习(三)