最短路径问题

PRoblem Description

Input

Output

Example Input

50 02 02 20 23 151 21 31 42 53 51 5
Example Output
3.41
DIJKSTRA算法：
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#define maxn 101#define max 9999999.9double df[maxn][maxn];double dist[maxn];int  book[maxn];int n,t;double min;void dijkstra(int vo){    int i,j,k,u;    for(i=0;i<=n;i++)    {        dist[i]=df[vo][i];    }    dist[vo]=0.0;    book[vo]=1;    for(i=1;i<=n;i++)    {        min=max;        u=vo;        for(j=1;j<=n;j++)        {            if(dist[j]<min&&book[j]==0)            {                min=dist[j];                u=j;            }        }        book[u]=1;        for(k=1;k<=n;k++)        {            if(dist[k]>dist[u]+df[u][k]&&df[u][k]<max&&book[k]==0)            {                dist[k]=dist[u]+df[u][k];            }        }    }}int main(){    int i,m,u,v,x,y,s;    int a[maxn][2];    memset(df,max,sizeof(df));    scanf("%d",&n);    for(i=0;i<=n;i++)    {        df[i][i]=0.0;    }    for(i=1;i<=n;i++)    {        scanf("%d %d",&a[i][0],&a[i][1]);    }    scanf("%d",&m);    while(m--)    {        scanf("%d%d",&u,&v);        x=(a[u][0]-a[v][0])*(a[u][0]-a[v][0]);        y=(a[u][1]-a[v][1])*(a[u][1]-a[v][1]);        df[u][v]=df[v][u]=sqrt(x+y);    }    scanf("%d%d",&s,&t);    dijkstra(s);    printf("%.2lf/n",dist[t]);    return 0;}
BELLMAN算法：
#include<stdio.h>#include<string.h>#include<math.h>#define maxn 101#define max 9999999.9double df[maxn][maxn];double dist[maxn];int n,t;void bellman(int s){    int i,j,k,u;    for(i=1;i<=n;i++)    {        dist[i]=df[s][i];    }    for(i=1;i<n;i++)    {        for(j=1;j<=n;j++)        {            if(j!=s)            {                for(k=1;k<=n;k++)                {                    if(df[k][j]<max&&dist[j]>dist[k]+df[k][j])                    {                        dist[j]=dist[k]+df[k][j];                    }                }            }        }    }}int main(){    int i,m,u,v,x,y,s;    int a[maxn][2];    memset(df,max,sizeof(df));    scanf("%d",&n);    for(i=0;i<=n;i++)    {        df[i][i]=0.0;    }    for(i=1;i<=n;i++)    {        scanf("%d%d",&a[i][0],&a[i][1]);    }    scanf("%d",&m);    while(m--)    {        scanf("%d%d",&u,&v);        x=(a[u][0]-a[v][0])*(a[u][0]-a[v][0]);        y=(a[u][1]-a[v][1])*(a[u][1]-a[v][1]);        df[u][v]=df[v][u]=sqrt(x+y);    }    scanf("%d%d",&s,&t);    bellman(s);    printf("%.2lf/n",dist[t]);    return 0;}