poj2387-最短路-dijkstra

原题连接

题意

给定n个点以及m条无向边，
求第n点到第一个点的最小距离
纯粹的迪杰斯特拉模板题

思路

迪杰斯特拉：在所有的路都是正数情况下，找从n点开始到达其他点的最短距离
首先从n点开始，把能到达的点全部存储在dist中
每一次从dist中找出一个最小值，
这个最小值表示当前n点能到达的最近的点
在这个点走向其他点，检验能否通过这个最小点减小到其他点的距离

注意，可能a,b之间存在多条边，需要存一个最小的路径

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1100;

int map[N][N];//存储路径的长度，路是双向的
int dist[N];//dist[i]表示从第n点到第i点的最短距离 
int t,n; 
int flag[N];//标记，标记哪些点已经是找到最短距离了 

int find()
{
    int i,j,l;
    //将到达其他点的最短路径初始化 
    for(i=1;i<=n;i++) dist[i]=map[n][i];
    dist[n]=0;//n点到达n点的距离是0；
    flag[n]=1; 
    
    //一共需要找n-1个点的最短距离 
    for(l=1;l<n;l++){
        int k=-1;//k存储当前n点到达其他点的最短距离 
        int maxv=0x3f3f3f3f;//设置最大值 
        for(i=1;i<=n;i++){
            //如果当前点还没找过，且小于之前找过的最小值 
            if(flag[i]==0 && maxv>dist[i]){
                //则将k赋值，表示找到的最小的点 
                k=i;
                maxv=dist[i];
            } 
        } 
        
        //如果k==-1.则表示找了一圈，已经没有符合条件的最短的路了 
        if(k==-1){
            break;//直接退出 
        } 
        
        flag[k]=1;//找到的最短路标记一下 
        for(i=1;i<=n;i++){
            if(!flag[i] && maxv+map[k][i]<dist[i]){
                dist[i]=maxv+map[k][i];
            }
        } 
    } 
    return dist[1];
}
int main()
{
    int i,j;
    while(scanf("%d%d",&t,&n)!=EOF)
    {
        //将所有路都初始化为一个极大值 
        memset(map,0x3f,sizeof map); 
        
        int a,b,c;
        while(t--){
            scanf("%d%d%d",&a,&b,&c);
            map[b][a]=map[a][b]=min(map[a][b],c);
        } 
        printf("%d\n",find());
    }
    return 0;
}