Hoj 2047 106 miles to Chicago
Dijkstra.
只不过是把原先的普遍的最短单源路径当作最大单源路径来求。且运算符是乘法而不是加法。用Double来存储,细节部分需要雕琢一下再提交。
题目:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h>
#include <algorithm>
using namespace std;
double map[102][102];
double dist[102];
int visited[102];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m;
while(scanf(" %d %d",&n,&m) == 2)
{
memset(map,0,sizeof(map));
for(int i=0; i<m; i++)
{
int a,b;
double p;
scanf(" %d %d %lf",&a,&b,&p);
map[a-1][b-1] = map[b-1][a-1] = p;
}
for(int i=0; i<n; i++)
{
map[i][i] = 100;
}
memset(dist,0,sizeof(dist));
memset(visited,0,sizeof(visited));
dist[0] = 100;
for(int i=0; i<n; i++)
{
double max = 0;
int k = 0;
for(int j=0; j<n; j++)
{
if(visited[j] == 0 && dist[j]>max)
{
max = dist[j];
k = j;
}
}
visited[k] = 1;
for(int j=0; j<n; j++)
{
if(dist[j] < dist[k] * map[k][j]/100)
{
dist[j] = dist[k] * map[k][j]/100;
}
}
}
printf("%.6lf percent\n",dist[n-1]);
}
return 0;
}
补充:软件开发 , C++ ,