hdu 1874 畅通工程续（求最短距离，dijkstra,floyd）

/************************************************************************/
/*     
        hdu  畅通工程续
        dijkstra求起始点到目标点最短距离
        题目大意：求这些村子中从起始位置到目标点的最短距离
        解题思路：dijkstra算法，求图中两个点的最短距离,

dijkstra算法不同于prim算法，prim算法是求虽小生成树，

不断地把点最近的点加入到集合中；而dijkstra算法是求源点到目标点的最短距离。
*/
/************************************************************************/

#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MAX 0xfffffff
const int N = 201;

int dj[N],map[N][N],vis[N];
int n,m,x,y,len,i,j;


void DJ(int start,int end)
{
    int min,k;
    int t = n;
    int cur = start;
    
    for(i=0;i<n;dj[i++]=MAX); 
    dj[start] = 0;
    while(1)
    {
        min = MAX;
        vis[cur] = 1;
        for(i = 0; i < n; i++)
        {
            if(vis[i]==1)continue;
            if(dj[i] > map[i][cur] + dj[cur])//////////
                dj[i] = map[i][cur] + dj[cur];
            if(min>dj[i])
            {
                min = dj[i];
                k = i;
            }
        }
        cur = k;
        if(cur == end)break;
        if(min == MAX)break;
    }
    printf("%d\n",dj[end]<MAX?dj[end]:-1);
}

int main()
{
    while(scanf("%d%d",&n,&m)!= EOF)
    {
        memset(vis,0,sizeof(vis));
        for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            map[i][j] = (i==j?0:MAX);
        }
        for (i = 1; i <= m; i++)
        {
            scanf("%d%d%d",&x,&y,&len);
            map[x][y] = map[y][x] = (map[x][y]<len?map[x][y]:len);
        }
        scanf("%d%d",&x,&y);
        DJ(x,y);
    }
    return 0;
}

/************************************************************************/
/*     
        hdu  畅通工程续
        floyd 求起始点到目标点最短距离
        题目大意：求这些村子中从起始位置到目标点的最短距离
        解题思路：floyd 算法，求图中两个点的最短距离
        floyd算法就是在整个图中扫描，看点 i 到 j 的距离和
        （点 i 到点 k 的距离）+（点 k 到点 j 的距离）两者哪个较小，
        把小的存入map[i][j]中即可。
*/
/************************************************************************/

#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MIN(a,b) a<b?a:b
#define MAX 0xfffffff
const int N = 201;

int map[N][N];
int n,m,x,y,len,i,j;


void floyd(int start,int end)
{
    int k;
    for (k = 0; k < n; k++)
    {
        for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        map[i][j] = MIN(map[i][j],map[i][k]+map[k][j]);
    }
    printf("%d\n",map[start][end]<MAX?map[start][end]:-1);
}

int main()
{
    while(scanf("%d%d",&n,&m)!= EOF)
    {
        for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            map[i][j] = (i==j?0:MAX);
        }
        for (i = 1; i <= m; i++)
        {
            scanf("%d%d%d",&x,&y,&len);
            map[x][y] = map[y][x] = (map[x][y]<len?map[x][y]:len);
        }
        scanf("%d%d",&x,&y);
        floyd(x,y);
    }
    return 0;
}