[数据结构与算法]代码解析 最短路径 排序

问题 C: 有向图的最短路径长度

题目描述 已知一个有向图，每个边都有一个正整数表示边长，请编程求出其中两个顶点间的最短路径长度。

Floyd（弗洛伊德算法）

Floyd弗洛伊德算法用于解决多点之间的最短路径问题，而且可以很好地解决负权边问题（也就是边的值为负），时间复杂度O(N^3)，可以完美解决数据范围较小时的最短路径

Floyd的主要思想
在两点之间，这两点之间的距离有可能会比经过一些中转点要长，也就是说我们直接从A到B可能是10km，但是如果我们先从A到C，再从C到B，这样距离有可能会缩短到8km，所以我们只需要枚举中转点即可，只要起始点到中转点的距离加上中转点到目标点的距离大于直接从起始点到目标点，那么我们就更新这两点之间的距离
我们使用d这个二维数组来存储两点之间的最短距离，d[x][y]就是x到y的最短距离

初始化
最开始的时候，我们每两点之间的距离都设为无穷大，也就是memset(d,0x3f,sizeof(d))这句代码，意思就是把d中所有元素都初始化为（16进制数3f3f3f3f，转化为10进制就是很大的一个数）然后我们自身到自身的距离再设为0，因为这里面的地点都是字母，我们做一个从字母到数字的转化（也就是A就变成1，B就变成2以此类推）
最后直接输出d[起始点][目标点]就可以了
代码

#include<iostream>
#include<cstring>
using namespace std;
int d[30][30];
int main() {
    int m,n;
    cin>>m>>n;
    char a,b;
    int w;
    memset(d,0x3f,sizeof(d));
    for(int i=1;i<=m;i++) d[i][i]=0;
    for(int i=1;i<=n;i++) {
        cin>>a>>b>>w;
        d[a-'A'+1][b-'A'+1] = w;
        d[b-'A'+1][a-'A'+1] = w;
    }
    for(int k=1;k<=m;k++) {
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
                if(d[i][k]+d[k][j]<d[i][j])
                    d[i][j] = d[i][k]+d[k][j];
    }
    cin>>a>>b;
    cout<<d[a-'A'+1][b-'A'+1];
    return 0;
}

问题 D: 有向图的最短路径

题目描述 已知一个有向图，每个边都有一个正整数表示边长，请编程求出其中两个顶点间的最短路径长度。

Floyd很难解决路径问题

Floyd适合求出任意两点之间的距离，但是如果求得起始点到目标点的路径呢，我们就需要想一些其他的算法，就比如常见的dijkstra(迪杰斯特拉算法)

dijkstra迪杰斯特拉算法

迪杰斯特拉算法其实是一种贪心算法（什么是贪心算法？也就是我们当前可以选择最优解，我们一直选择当前最优解，最后当前最优解可以转化为全局最优解，那么就可以使用贪心算法来解决）我们从起始点开始遍历，使用一个vis数组来判断我们是否已经遍历过当前的结点（如果vis[i]为true，就表明当前编号为i的结点已经遍历过，我们就可以直接跳过不用遍历了，每次遍历一个结点，都把vis设为true）

当前遍历到的结点，我们使用数组dis来存储当前点到起始点的距离，最开始初始化为一个无穷大，起始点到起始点初始化为0，遍历当前结点所连接的所有边，如果边的终点到起始点的距离比dis更大，那么我们就更新，同时放到一个优先队列里面，优先队列保证我们每次都取到最优的结点

如何输出路径？

对于任意一个结点，我们每次找到更短的路径时，我们都用pre数组记录到这个结点的前一个结点的编号，最后我们每一个结点都会有一个到自己的前驱节点的编号，我们从最后的结点开始向前找，一直找到起始点，然后倒序输出即可，这里我使用了递归的算法，a表示起始点，b表示当前已经到达哪个结点，如果a==b就表明已经从终止点找到了起始点，如果a≠b，我们就继续递归找a和b的前驱，倒序输出记得把输出放在递归函数的后面

代码大家看个乐呵就行了，比较难理解，主要讲思路

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct edge {
    char a,b;
    int w,next;
}e[105];
int cnt,dis[105],head[105];
bool vis[105];
int pre[105];
struct node {
    int w,now;
    inline bool operator <(const node &x) const {
        return w>x.w;
    }
};
priority_queue<node> q;
void add(char a,char b,int w) {
    e[++cnt].a = a;
    e[cnt].b = b;
    e[cnt].w = w;
    e[cnt].next = head[a-'A'+1];
    head[a-'A'+1] = cnt;
}
void dijkstra(char fir) {
    dis[fir-'A'+1]=0;
    node x = {0,fir-'A'+1};
    char v;
    q.push(x);
    while(!q.empty()) {
        x = q.top();
        q.pop();
        int u = x.now;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=head[u];i;i=e[i].next) {
            v = e[i].b;
            if(dis[v-'A'+1]>dis[u]+e[i].w) {
                dis[v-'A'+1] = dis[u]+e[i].w;
                pre[v-'A'+1] = u;
                x = {dis[v-'A'+1],v-'A'+1};
                q.push(x);
            }
        }
    }
}
void findPath(int a,int b) {
    if(a==b) {
        cout<<char(a+'A'-1)<<" ";
        return;
    }
    findPath(a,pre[b]);
    cout<<char(b+'A'-1)<<" ";
}
int main() {
    int m,n;
    cin>>m>>n;
    char a,b;
    int w;
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++) {
        cin>>a>>b>>w;
        add(a,b,w);
    }
    cin>>a>>b;
    dijkstra(a);
    findPath(a-'A'+1,b-'A'+1);
    return 0;
}

问题 E: 5个数的从大到小排序

题目描述 数学课上，老师公布了一个小组的5名同学的成绩，你能编程把成绩从大到小排序吗，以便老师知道考试名次？

水题

直接用sort一排序就可以了，自己编一个cmp比较函数用于从大到小排序（sort默认从大到小，不需要编写cmp）

#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int x,int y) {
    return x>y;
}
int main() {
    int a[6];
    for(int i=0;i<5;i++) {
        scanf("%d",&a[i]);
    }
    sort(a,a+5,cmp);
    for(int i=0;i<5;i++) {
        printf("%d ",a[i]);
    }
    return 0;
}

问题 F: 病人排队
题目描述
病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：
1.老年人（年龄 >= 60岁）比非老年人优先看病。
2.老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。
3.非老年人按登记的先后顺序看病。

编写一个比较复杂的cmp比较函数即可

对于每一位病人，我们用一个结构体来存储，从前到后给每个病人一个前后顺序的编号，第一种情况两个病人都是老年人，并且年龄相同，我们就按照编号从小到大，第二种情况两个病人都不是老年人，那么我们直接按照编号排序，第三种情况，两个都是老年人且年龄不同，我们按照年龄降序，第四种情况，一个老年人一个年轻人，还是年龄降序，第三种和第四种都是按照年龄降序，我们合并为一种情况就是else

#include<cstdio>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
struct person {
    string id;
    int age,num;
}p[105];
bool cmp(person x,person y) {
    if(x.age==y.age&&x.age>=60) return x.num<y.num;
    if(x.age<60&&y.age<60) return x.num<y.num;
    return x.age>y.age;
}
int main() {
    int n,age;
    scanf("%d",&n);
    string x;
    for(int i=1;i<=n;i++) {
        cin>>p[i].id>>p[i].age;
        p[i].num = i;
    }
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++) {
        cout<<p[i].id<<'\n';
    }
    return 0;
}