机试day11

最短路径：求图G中两个特定顶点之间最短路径长度

应用包括：求两个城市间最短行车距离等

经典算法：Dijkstra算法，将顶点集合V分成两个集合S和T

• S：已确定的顶点集合，初始只含源点s
• T=V-S：尚未确定的顶点集合

算法反复从集合T中选择当前源点s最近的顶点u，将u加入集合S，然后对所有从u发出的边进行松弛操作（贪心策略）

畅通工程续

题目：已知起点终点，计算最短行走距离，每组第一行包含两个正整数N和M（0<N<200，0<M<1000），分别代表城镇数目和已修建道路数目。接下来是M行道路信息，每行A、B、X表示AB间一条道路距离X。再接下来一行有两个整数S、T代表起点终点

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 200;
const int INF = INT_MAX;    // 无穷大

struct Edge {
    int to, length;
    Edge(int t, int l): to(t), length(l) {}
};

struct Point {
    int number, distance;
    Point(int n, int d): number(n), distance(d) {}
    bool operator< (const Point& p) const {
        return distance > p.distance;
    }
};

vector<Edge> graph[MAXN];   // 邻接表实现的图
int dis[MAXN];              // 源点到各点距离

void Dijkstra(int s) {
    priority_queue<Point> myPriorityQueue;
    dis[s] = 0;
    myPriorityQueue.push(Point(s, dis[s]));
    while (!myPriorityQueue.empty()) {
        int u = myPriorityQueue.top().number;
        myPriorityQueue.pop();
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].to;
            int d = graph[u][i].length;
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                myPriorityQueue.push(Point(v, dis[v]));
            }
        }
    
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        memset(graph, 0, sizeof(graph));
        fill(dis, dis + n, INF);    // 距离初始化为无穷
        while (m--) {
            int from, to, length;
            cin >> from >> to >> length;
            graph[from].push_back(Edge(to, length));
            graph[to].push_back(Edge(from, length));
        }
        int s, t;
        cin >> s >> t;
        Dijkstra(s);
        if (dis[t] == INF) 
            dis[t] = -1;
        cout << dis[t] << endl;
    }
}

最短路径问题

描述

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入描述：

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t)

输出描述：

输出 一行有两个数， 最短距离及其花费。

思路：在上一题的基础上增加cost，因此需要改变小于号的重载，先比较距离，如果相等再比较花费

同时需要注意有俩种满足最小路径的条件，一种是距离更小，一种是距离相等但花费更少

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1000;
const int INF = INT_MAX;

struct Edge {
    int to, length, cost;
    Edge(int t, int l, int c): to(t), length(l), cost(c) {}
};

struct Point {
    int number, distance, cost;
    Point(int n, int d, int c): number(n), distance(d), cost(c) {} 
    bool operator< (const Point& p) const {
        if (distance != p.distance)
            return distance > p.distance;
        else
            return cost > p.cost;
    }
};

vector<Edge> graph[MAXN];
int dis[MAXN], cost[MAXN];

void Dijstra(int s) {
    priority_queue<Point> myPriorityQueue;
    dis[s] = 0, cost[s] = 0;
    myPriorityQueue.push(Point(s, dis[s], cost[s]));
    while (!myPriorityQueue.empty()) {
        int u = myPriorityQueue.top().number;
        myPriorityQueue.pop();
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].to;
            int l = graph[u][i].length;
            int c = graph[u][i].cost;
            if (dis[v] > dis[u] + l || (dis[v] == dis[u] + l && cost[v] > cost[u] + c)) {
                dis[v] = dis[u] + l;
                cost[v] = cost[u] + c;
                myPriorityQueue.push(Point(v, dis[v], cost[v]));
            }
        }
    }
}


int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;
        memset(graph, 0, sizeof(graph));
        fill(dis, dis + n + 1, INF);
        fill(cost, cost + n + 1, INF);
        int a, b, d, p;
        while (m--) {
            cin >> a >> b >> d >> p;
            graph[a].push_back(Edge(b, d, p));
            graph[b].push_back(Edge(a, d, p));
        }
        int s, t;
        cin >> s >> t;
        Dijstra(s);
        cout << dis[t] << " " << cost[t] << endl;
    }
}