4.3算法之图论 726:ROADS

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

思路

狄杰斯特拉直接改一下,基于优先级队列
Road 设置为二关键字排序
优先级队列 push 时只 push cost 小于等于 k 的 Road,则队列头部 Road.to 为 n 时必为满足 k 的最短路

源码

//
//  726.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <algorithm>
#define INT_MAX 999999999
using namespace std;
int k,n,r;
struct Road{
    int to,d,c;
    Road(int to,int d,int c):to(to),d(d),c(c){}
    bool operator < (const Road &r) const {
        if(d==r.d)return c<r.c;
        return d > r.d;
    }
};
vector<vector<bool>> vis;
vector<int> dis;
vector<vector<Road>> edge;


int main(){
    cin >> k >> n >> r;
    edge.resize(n+1,vector<Road>());
    dis.resize(n+1,INT_MAX);
    vis.resize(n+1,vector<bool>(n+1,false));
    for(int i = 0;i < r;++i){
        int a,b,c,d;
        cin >> a>>b>>c>>d;
        edge[a].push_back(Road(b,c,d));
    }

    priority_queue<Road> q;
    q.push(Road(1,0,0));
    while(!q.empty()){
        Road road = q.top();
        q.pop();
        if(road.to==n){
            cout <<road.d;
            return 0;
        }
        int internal = road.to;
        for(int j = 0;j < edge[internal].size();++j){
            int des = edge[road.to][j].to;
            if(k>=road.c+edge[road.to][j].c){
                q.push(Road(des,road.d+edge[road.to][j].d,road.c+edge[road.to][j].c));
            }
        }
    }

    return 0;
}

发表评论

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