HDU-1874-畅通工程续 (队列优化)

畅通工程续

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 53520 Accepted Submission(s): 19997

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算法中可以得知，原算法是遍历除起点外的n-1个节点，筛选出未标记过且最小权值的点，然后利用这个点更新dist数组中的其他点，使其他点利用这个最短路松弛之后也实现最短路，直到所有点都到达最短路。
注意这个过程是可以进行优化的，在筛选最小权值的点时，可以用优先队列直接弹出，而不必每次都遍历数组。在取出最小权值的点后，将新的dist更新，并向队列中塞入新的点，使到达各点的权值中最小的始终在队首。这里和利用二维数组邻接矩阵不同的是用了结构体同时存储到达某个点的权值以及点的序号，并且用动态数组来存储图，表示每个节点能够到达的所有点，以及从自己(动态数组下标)到达某个点的权值。

#include<stdio.h>///优先队列优化
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
const int N=208;
const int MAX=0x7fffffff;
int dist[N];///记录到达每个节点的最短路
int n,m,flag;
struct Edge
{
    int to,val;///点的标号以及到达此点需要的权值
    Edge(int a=0,int b=0):to(a),val(b){}///结构体构造函数
    bool operator <(const Edge &a)const///重载运算符
    {
        if(val==a.val)return to<a.to;
        return val>a.val;
    }
};
vector<Edge>v[N];///(结构体类型)动态数组做邻接矩阵
void dijkstra(int s)
{
    memset(dist,0x3f,sizeof(dist));///一开始到达所有节点的路程都是inf
    flag=dist[0];///用于判断无法到达的情况(-1)
    dist[s]=0;///到达起点的最短路为0
    priority_queue<Edge>q;///优先队列优化
    q.push(Edge(s,0));///将起始节点放入队列中
    while(!q.empty())
    {
        Edge top=q.top();
        q.pop();
        for(int i=0;i<v[top.to].size();i++)///遍历所有从当前点出发到达的所有节点
        {
            Edge tmp=v[top.to][i];
            if(dist[tmp.to]>top.val+tmp.val)///用当前节点松弛目的节点的最短路
            {
                dist[tmp.to]=top.val+tmp.val;
                q.push(Edge(tmp.to,dist[tmp.to]));///每次投入队列中的结构体都是直接构造的，并不是原先就存在的
            }                                     ///投入一个可以到达的点，权值取当前到达节点的已知最短路
        }
    }
}
int main()
{
    int i,j,k,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<=N;i++)v[i].clear();///清空数组
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&k);///这里结构体仅存储到达某个点的权值，至于谁到达这个点的权值，由动态数组下标存储
            v[x].push_back(Edge(y,k));///无向图
            v[y].push_back(Edge(x,k));
        }///相当于一个点到达另一个点的权值，由另一个点的结构体来存储，而动态数组存储所有自己能到的的点结构体，结构体内的权值也就是动态数组下标到达结构体内标号的权值
        int s,t;
        scanf("%d%d",&s,&t);
        dijkstra(s);
        printf("%d
",dist[t]==flag?-1:dist[t]);
    }
}

HDU-1874-畅通工程续 (队列优化)

相关推荐