Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我的WA代码，大虾们有空了进来分析分析：

Posted by 123454321 at 2007-08-05 09:02:57 on Problem 2472
```/*我的WA代码：结点从1开始计，maxn为最大结点数,
n为结点数，manint是无穷大, c[i][j] i到j的权，pre[]记录父结点,dist[i]源点到i的最短路径，s[]表示左边的集合*/
#include <iostream>
#include <stdio.h>
using namespace std;

const int maxn = 102;
int manint = 99999999;
double c[maxn][maxn],dist[maxn];
int prev[maxn],n;
double ans;
void dijkstra(int v)//原点是v
{
bool s[maxn];  register int i,j;

for(i=1;i<=n;i++)
{
dist[i] = c[v][i];
s[i] = 0;
if(dist[i]==manint)//v to i没有边
prev[i] = 0;
else
prev[i] = v;
}
s[v] = 1; dist[v] = 0;
for(i=1;i<n;i++)
{
double temp = manint;
int u = v;
for(j=1;j<=n;j++)
if(!s[j]&&dist[j]>=0&&dist[j]<temp)
{
u = j;
temp = dist[j];
}
s[u] = 1;
for(j=1;j<=n;j++)
if(!s[j]&&c[u][j]<manint)
{
double newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}

int main()
{
register int i,j;
int edges;
int a,b;
double percent;
while(cin>>n&&n)
{
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
c[i][j]=manint;
cin>>edges;
for(i=1;i<=edges;i++)
{
cin>>a>>b>>percent;
c[a][b]=c[b][a]=1-percent/100;
}
dijkstra(1);
ans=1.0;
int k=n;
while(k!=1)
{
ans*=(1-c[k][prev[k]]);
k=prev[k];
}
printf("%.6lf percent\n",ans*100);
}
return 0;
}

```

Followed by: