4.3算法之图论 799 Heavy Transportation

http://noi.openjudge.cn/ch0403/799/

思路

狄杰斯特拉改一下松弛函数即可
-1代表路径不通

AC源码

//
//  799.cpp
//  test
//
//  Created by bytedance on 2020/7/15.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#define INT_MAX 999999
#define close -1
using namespace std;

struct Node{
    int d,u;
    Node(int d,int u):d(d),u(u){}
    bool operator <(const Node & a) const{
        return d<a.d;
    }
};
int main(){
    int n;
    cin >> n;
    int vs,es;

    for(int i = 1;i <= n;++i){
        cin >> vs >> es;
        vector<vector<int>> e(vs+1,vector<int>(vs+1,-1));
        vector<bool> vis(vs+1,false);
        vector<int> dis(vs+1,-1);
        while(es--){
            int a,b,c;
            cin >> a>>b>>c;
            e[a][b]=c;
            e[b][a]=c;
        }
        //dijkstra

        priority_queue<Node> q;
        q.push(Node(-1,1));
        dis[1] = INT_MAX;
        while(!q.empty()){
            Node t = q.top();
            q.pop();
            int d = t.d;
            int u = t.u;
            //cout << d<<endl;
            if(vis[u])continue;
            vis[u]=true;
            for(int j = 1;j <= vs; ++j){
                if(!vis[j]&&dis[j]<min(dis[u],e[u][j])){
                    dis[j]=min(dis[u],e[u][j]);
                    q.push(Node(dis[j],j));
                }
            }
        }
        cout <<"Scenario #"<<i<<":"<<endl<<dis[vs]<<endl<<endl;
    }
    return 0;
}

发表评论

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