Time limit1000 ms

Memory limit32768 kB

 

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

3

2

题解 最短路的模版题，我用的dijkstra，简单的说就是先找第一个点的所有的连它的边的最短的那条，把它加进去后，把连进去的点和原先的点看成同一个点，在找下一个离这个边最短的点，

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

#define PI 3.14159265358979323846264338327950

const int x=;

const int INF=;

int cost[x][x],n,m;

int d[x];

bool vis[x];

void dijkstra(int f )

{

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

        d[i] = INF;

    d[f] = ;

    memset(vis, , sizeof(vis));

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

    {

        int u=-;

        for(int j=;j<=n;++j)

            if(!vis[j])

            {

                if(u==- || d[j]<d[u])

                    u=j;

            }

        vis[u]=;

        for(int j=; j<=n; ++j)

            if(!vis[j])

            {

            int tmp = d[u] + cost[u][j];

            if(tmp<d[j]) d[j] = tmp;

            }

    }

}

int main(){

    int a,b,c;

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

    {

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

        {

            cost[i][i]=INF;

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

                cost[i][j]=cost[j][i]=INF;

        }

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

        {

            scanf("%d %d %d",&a,&b,&c);

             cost[a][b]=cost[b][a]=c;

        }

        dijkstra();

        printf("%d\n",d[n]);

    }

}