题意：

有n个城市，有m条路，给出每条路的出发和结束的城市及长度，求从第一个城市到最后一个城市的最短路。按格式输出。

power oj 2443

题解：

标准dijk算法。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=505;

typedef long long LL;

int W[maxn][maxn];

int  vis[maxn];

int dis[maxn];

int n,m;

void init()

{

    for(int i=0;i<maxn;i++)

    {

        for(int j=0;j<maxn;j++)

            W[i][j]=INF;

        W[i][i]=0;

    }

    memset(vis,0,sizeof(vis));

}

void dijk()

{

    for(int i=0;i<n;i++) dis[i]=(i==0?0:INF);

    for(int i = 0;i < n;i++)

    {

        int m = INF , x=0;

        for(int y = 0;y <n;y++) if(!vis[y] && dis[y] <= m) m = dis[x=y];

        vis[x] = true;

        for(int y = 0;y < n;y++) dis[y]=min(dis[y],dis[x]+W[x][y]);

    }

}

int main()

{

    double sp1,sp2;

    int u,v,d;

    while(~scanf("%d%d",&n,&m))

    {

        init();

        for(int i=0;i<m;i++)

        {

            scanf("%d%d%d",&u,&v,&d);

            if(W[u][v]>d&&u!=v)

                W[u][v]=W[v][u]=d;

        }

        dijk();

        scanf("%lf%lf",&sp1,&sp2);

        if(dis[n-1]>=INF)

            printf("There is a tie!\n");

        else

        {

            printf("%.1lf %.1lf\n",(double)dis[n-1]/sp1+10.00,(double)dis[n-1]/sp2);

        }

    }

    return 0;

}