当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,