P1339 热浪 (优先队列+dijkstra)模板

清疚 2023-06-21 14:26 19阅读 0赞

##### 题目描述 #####

> 有一个 nn 个点 mm 条边的无向图，请求出从 ss 到 tt 的最短路长度。

--------------------

###### 输入格式 ######

> 第一行四个正整数 n,m,s,tn,m,s,t。 接下来 mm 行，每行三个正整数 u,v,wu,v,w，表示一条连接 u,vu,v，长为ww 的边。

###### 输出格式 ######

> 输出一行一个整数，表示答案。

--------------------

##### 输入输出样例 #####

###### 输入 ######

7 11 5 4
    2 4 2
    1 4 3
    7 2 2
    3 4 3
    5 7 5
    7 3 3
    6 1 1
    6 3 4
    2 4 3
    5 6 3
    7 2 1

###### 输出 ######

--------------------

##### 说明/提示 #####

> 【数据范围】 对于 100%100% 的数据，1\\le n \\le 25001≤n≤2500，1\\le m \\le  
> 62001≤m≤6200，1\\le w \\le 10001≤w≤1000。
> 
> 【样例说明】 5 \\to 6 \\to 1 \\to 45→6→1→4 为最短路，长度为 3+1+3 = 73+1+3=7。

--------------------

##### 代码实现(模板) #####

#include<bits/stdc++.h>
    using namespace std;
    
    const int MAXV = 3000;
    const int INF = 0x3f3f3f3f;
    
    int n, m, s, t;
    
    struct edge{ 
        int u;
        int v;
        int w;
        edge(int _v, int _w): v(_v), w(_w) { }
        edge(){ }
    };
    struct node{ 
        int v;
        int d;
        friend bool operator < (const node &a, const node &b)  //重载<号，定义优先队列的堆排序方式
        { 
            return a.d > b.d;
        }
        node(int _v, int _d): v(_v), d(_d) { }
        node() { }
    };
    vector<edge> G[MAXV];      //邻接表存每条边
    priority_queue<node> pq;
    int d[MAXV];
    bool vis[MAXV];
    
    void dijkstra()
    { 
        fill(d, d+MAXV, INF);
        fill(vis, vis+MAXV, false);
        pq.push(node(s,0));
        d[s] = 0;
        while(!pq.empty())
        { 
            int u = pq.top().v;
            pq.pop();
            if(vis[u])
                continue;
            vis[u] = true;
            if(u == t)
            { 
                printf("%d",d[t]);
                break;
            }
            for(int i = 0; i < G[u].size(); i++)
            { 
                int v = G[u][i].v;
                int l = G[u][i].w;
                if(d[u]+l < d[v])
                { 
                    d[v] = d[u]+l;
                    pq.push(node(v, d[v]));
                }
            }
        }
    }
    int main()
    { 
        scanf("%d%d%d%d", &n, &m, &s, &t);
        for(int i = 1; i <= m; i++)
        { 
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            G[a].push_back(edge(b, c));
            G[b].push_back(edge(a, c));
        }
        dijkstra();
        return 0;
    }