NOI 2387:Til the Cows Come Home

题目

http://bailian.openjudge.cn/practice/2387/

思路

狄杰斯特拉,优先级队列和 d 数组保持同步即可,使用邻接表的话,Edge 中的 from 字段可以省略

源码

//
//  2387.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#define inf 99999999
using namespace std;
struct Edge{
    int from,to,dis;
    Edge(int from,int to,int dis):from(from),to(to),dis(dis){};
    bool operator < (const Edge &e) const{
        return e.dis<dis;
    }
};

int n, t;

int main(){
    cin >> t >> n;
    vector<vector<Edge>> edges(n+1,vector<Edge>());
    priority_queue<Edge> q;
    vector<int> d(n+1,inf);
    vector<bool> done(n+1);
    while(t--){
        int a,b,c;
        cin >> a>>b>>c;
        Edge e(a,b,c);
        edges[a].push_back(e);
        Edge e2(b,a,c);
        edges[b].push_back(e2);
    }
    //边读入ok,初始化距离数组
    q.push(Edge(1,1,0));
    d[1]=0;
    while(!q.empty()){
        int node  = q.top().to;q.pop();
        if(done[node])continue;
        done[node] = true;
        for(int i = 0;i < edges[node].size();++i){
            Edge e = edges[node][i];
            if(d[e.to]>d[node]+e.dis){
                d[e.to] = d[node]+e.dis;
                q.push(Edge(1,e.to,d[e.to]));
            }
        }
    }
    cout << d[n];
    return 0;
}
发布于 :NOI

发表评论

电子邮件地址不会被公开。 必填项已用*标注