概率上的最長路可以使用Dijkstra解決，因為乘以一個[0,1]的數不會比原來的值大。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/2 16:42:25
* File Name: poj2472.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(200);
const double kEps(1e-11);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(107);
int n,m;
double g[kMaxn][kMaxn],d[kMaxn];
void Dijkstra()
{
bool visited[kMaxn];
memset(visited,false,sizeof(visited));
d[1]=1;
for(int i=2;i<=n;i++)
d[i]=0;
for(int i=1;i<=n;i++)
{
int v(-1);
double w(0);
for(int j=1;j<=n;j++)
if(!visited[j] && w<d[j])
{
v=j;
w=d[j];
}
if(v==-1)
break;
visited[v]=true;
for(int j=1;j<=n;j++)
if(d[j]<d[v]*g[v][j])
d[j]=d[v]*g[v][j];
}
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1 && n)
{
memset(g,0,sizeof(g));
scanf("%d",&m);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u][v]=g[v][u]=w/100.0;
}
Dijkstra();
printf("%.6f percent\n",d[n]*100);
}
return 0;
}
posted on 2011-08-02 18:18
lee1r 閱讀(302)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論