题目描述

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。 给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

思路

一个单源最短路
O(n^2)

#include <stdio.h>
#define maxn 3001
#define INF 0x7f7f7f7f
#define min(x,y) x<y?x:y
int a[maxn][maxn],d[7001],f[7001];
int main()
{
    int n,m,s,e;
    scanf("%d%d%d%d",&n,&m,&s,&e);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            a[i][j]=INF;
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if (a[x][y]>z||a[x][y]==0)
        {
            a[x][y]=z;
            a[y][x]=z;
        }
    }
    f[s]=1;
    for (int i=1;i<=n;i++)
        d[i]=a[s][i];
    int u=0;
    do
    {
        u=0;
        int mi=INF;
        for (int i=1;i<=n;i++)
            if (f[i]==0&&d[i]<mi)
            {
                u=i;
                mi=d[i];
            }
        if (u!=0)
        {
            f[u]=1;
            for (int i=1;i<=n;i++)
                if (f[i]==0&&d[u]+a[u][i]<d[i]) 
                {
                    d[i]=d[u]+a[u][i];
                }
        }
    }
    while (u!=0);
    printf("%d\n",d[e]);
}