题目

Problem Description

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。

现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input

本题目包含多组数据，请处理到文件结束。

每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。

接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。

再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output

对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input

3 3

0 1 1

0 2 3

1 2 1

0 2

3 1

0 1 1

1 2
Sample Output

2

-1

题意

找最短路，用dijkstra

dijkstra理解

void dijkstra(int s)//贪心和dp
{
    memset(dis,0x3f,sizeof(dis));
    //起点 到 其他点的距离初始化为INF
    
    memset(vis,0,sizeof(vis));
    //vis[i]=0/1 ：0==i点未被遍历 , 1==i点已被遍历(已确定是最短路)
	
    for(int i=0; i<N; i++) //先从起点开始计算到周围点的距离
        dis[i]=road[s][i];
    vis[s]=1;//起点已经被遍历

    for(int i=0; i<N-1; i++) {
    //最后一个点连接的边 已经被 这些边连接的其他点遍历完了
        int min_d=INF,k;
        //找到距离起点s 最近的 未被访问过的点 作为新起点k，
        for(int j=0; j<N; j++) {
            if(vis[j]==0&&dis[j]<min_d)
                min_d=dis[j] , k=j;
        }
        vis[k]=1;
        //点k已成为过起点
		/*点k是目前距离起点s最近的点，该点的距离都是以前vis[i]==1的点构成的
		无法再有其他点到该点的距离会比当前的值小*/
        for(int j=0; j<N; j++) {
        //将新起点周围未确定的点(vis[i]!=1的点)更新一遍
            if(vis[j]==0)
                dis[j]=min( dis[k]+road[k][j],dis[j]);
        }
    }
}

代码

#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int road[210][210];
int dis[210];
int vis[210];
int N,M;
int s,e,d;
int starttt,enddd;

void dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));

    for(int i=0; i<N; i++)
        dis[i]=road[s][i];
    vis[s]=1;

    for(int i=0; i<N-1; i++) {
        int min_d=INF,k;
        for(int j=0; j<N; j++) {
            if(vis[j]==0&&dis[j]<min_d)
                min_d=dis[j] , k=j;
        }
        vis[k]=1;

        for(int j=0; j<N; j++) {
            if(vis[j]==0)
                dis[j]=min( dis[k]+road[k][j],dis[j]);
        }

    }
}

int main() {
    while( cin >> N >> M ) {
        memset(road,0x3f,sizeof(road));
        for(int i=0;i<N;++i)
			road[i][i]=0;
	
        for(int i=1; i<=M; ++i) {
            cin >>s >>e >>d;
            if(d < road[s][e] )
                road[s][e]=road[e][s]=d;
        }
        cin >> starttt >>enddd;
        dijkstra(starttt);
        if(dis[enddd]==INF)
            cout << "-1"<<endl;
        else cout << dis[enddd]<<endl;
    }
    return 0;
}

HDU1874(dijkstra)题意代码

题目

题意

dijkstra理解

代码