short-path problem (Dijkstra) 分类： ACM TYPE 2014-09-01 23:51 111人阅读评论(0) 收藏

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int INF = 0x3fffffff;

int  g[1005][1005];

int m;

int Dijkstra(int s,int t)

{

    bool visit[1005];

    int dis[1005];

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

    {

        visit[i] = false;

        dis[i] = g[s][i];

    }

    visit[s] = true;

    int min = INF;

    int k;

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

    {

        min = INF;

        k = 1;

        for(int j = 1; j <= m; ++j)

        {

            if(!visit[j] && dis[j] < min)

            {

                min = dis[j];

                k = j;

            }

        }

        visit[k] = true;

        for(int j = 1; j <= m; ++j)

        {

            if(!visit[j] && dis[k] + g[k][j] < dis[j])

            {

                dis[j] = dis[k] + g[k][j];

            }

        }

    }

    return dis[t];

}

int main()

{

    int T, a, b, len;

    int s, t, p;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d", &m, &p);

        scanf("%d%d",&s,&t);

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

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

                g[i][j] = g[j][i] = INF;

        while(p--)

        {

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

            if(g[a][b] > len)

                g[a][b] = g[b][a] = len;

        }

        printf("%d\n", Dijkstra(s,t));

    }

    return 0;

}

Code From Nyoj 115

巴特西

short-path problem (Dijkstra) 分类： ACM TYPE 2014-09-01 23:51 111人阅读评论(0) 收藏

最新文章

热门文章

巴特西

short-path problem (Dijkstra) 分类： ACM TYPE 2014-09-01 23:51 111人阅读 评论(0) 收藏

最新文章

热门文章

short-path problem (Dijkstra) 分类： ACM TYPE 2014-09-01 23:51 111人阅读评论(0) 收藏