[Usaco2009 Oct]Heat Wave 热浪-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Usaco2009 Oct]Heat Wave 热浪。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

有一个 n个点 m 条边的无向图，请求出从 s 到 t 的最短路长度。

输入格式第一行四个正整数 n, m, s, t。接下来 m 行，每行三个正整数 u, v, w，表示一条连接 u, v 长为 w 的边。

1≤n≤2500，1≤m≤6200，1≤w≤1000。

输出格式

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

样例输入

Copy to Clipboard

样例输出文章来源地址https://www.toymoban.com/news/detail-623535.html

Copy to Clipboard

/*
 * @Description: To iterate is human, to recurse divine.
 * @Autor: Recursion
 * @Date: 2022-03-02 11:52:08
 * @LastEditTime: 2022-03-24 12:07:32
 */
#include <bits/stdc++.h>
#define Inf 2147483647
using namespace std;
int head[(int)1e6+10],cnt;
int dis[(int)1e6+10],vis[(int)1e6+10];
int n,m,s;

void init()
{
    for(int i = 1;i <= n;i ++)
        dis[i] = Inf;
}

struct edge{
    int to;
    int weight;
    int next;//终点，边权，同起点的上一条边的编号
}edge[(int)1e6+10];

struct node{
    int w;
    int now;
    //重载运算符把最小的元素放在堆顶（大根堆）
    bool operator <(const node &x)const
    {
        return w > x.w;
    }
};

priority_queue<node>q;

void add(int u,int v,int w)
{
    edge[++cnt].to = v;
    edge[cnt].weight = w;
    edge[cnt].next = head[u];//存储该点的下一条边
    head[u] = cnt;//更新目前该点的最后一条边（就是这一条边）
}

void dijkstra()
{ 
    for(int i = 1;i <= n;i ++)
        dis[i] = Inf;
    dis[s] = 0;
    q.push((node){0,s}); 
    while(!q.empty()){
        //堆为空所以节点都更新
        node x = q.top();
        q.pop();
        int u = x.now;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i = edge[i].next){
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].weight){
                dis[v] = dis[u] + edge[i].weight;
                q.push((node){dis[v],v});
            }
        }
    }
}

int main()
{
    int t;
    cin >> n >> m >> s >> t;
    init();
    for(int i = 1;i <= m;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        add(x,y,z);
        add(y,x,z);
    }
    //dijkstra();
    int pos = s;
    dis[pos] = 0;
    while(vis[pos] == 0){
        int minn = Inf;
        vis[pos] = 1;
        for(int i = head[pos];i!=0;i = edge[i].next){
            if(!vis[edge[i].to]&&(dis[edge[i].to] > dis[pos] + edge[i].weight))
                dis[edge[i].to] = dis[pos] + edge[i].weight;
        }
        for(int i = 1;i<=n;i++)
            if(dis[i] < minn&&vis[i] == 0){
                minn = dis[i];
                pos = i;
            }
    } 
    cout << dis[t] << endl;
    // for(int i = 1;i <= n;i ++)
    //     cout << dis[i] << " ";
}

到了这里，关于[Usaco2009 Oct]Heat Wave 热浪的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！