12.29最小生成数K算法复习（注意输入输出格式），校园最短路径（通过PRE实现路径输出，以及输入输出格式注意）

7-2 最小生成树-kruskal算法 分数 15

const int maxn = 1000;
struct edge {
    int u, v, w;
}e[maxn];
int n, m, f[30];
bool cmp(edge a, edge b) {
    return a.w < b.w;
}
int find(int x) {
    if (f[x] == x) {
        return x;
    }
    else {
        f[x] = find(f[x]);
        return f[x];
    }
}    //int arr[100];
    //int n;
    //cin >> n;
    //for (int i = 1; i <= n; i++)cin >> arr[i];
cin >> n >> m;
for (int i = 1; i <= n; i++)f[i] = i;
for (int i = 1; i <= m; i++) {
    cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; i++) {
    int a = find(e[i].u), b = find(e[i].v);
    if (a != b) {
        f[a] = b;
        if (e[i].u > e[i].v) { cout << e[i].v << "," << e[i].u << "," << e[i].w << endl; }
        else {
            cout << e[i].u << "," << e[i].v << "," << e[i].w << endl;
        }
    }
    else {
        continue;
    }
}

7-1 校园最短路径 分数 10

主要是怎么打印路径，以及输入的格式，怎么转换这个输入格式

用pre数组，用string,然后在string里，用find,用字符下标，都转换为int型

链式前向星+堆优化dij

用pre数组记录前驱节点的索引，就是在string里的下标，也通过string类里的find函数找到相应字符的下标

#include <iostream>
#include <vector>
#include <algorithm>
#include<stack>
#include<queue>
#include <unordered_map>
#include<string>
#include<cstdio>
#include<map>
using namespace std;
struct edge {
    int v, w, next;
}e[102];
int h[102], n, m, pre[102], dis[102], cnt = 0;
string s;
bool vis[102] = { 0 };
void add(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = h[u];
    h[u] = cnt;
}
void print(int x) {
    if (!x) {
        cout << s[0];
        return;
    }
    print(pre[x]);
    cout << "->" << s[x];
}
typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, greater<pii>>q;
int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < n; i++)dis[i] = 1e8;
    for (int i = 1; i <= m; i++) {
        string a;
        int w;
        cin >> a >> w;
        add(s.find(a[0]), s.find(a[1]), w);
        add(s.find(a[1]), s.find(a[0]), w);
    }
    dis[0] = 0, vis[0] = 1, pre[0] = -1;
    for (int i = h[0]; i; i = e[i].next) {
        dis[e[i].v] = e[i].w;
        q.push({ dis[e[i].v],e[i].v });
        pre[e[i].v] = 0;
    }
    while (!q.empty()) {
        int d = q.top().first, u = q.top().second;
        q.pop();
        if (vis[u])continue;
        vis[u] = 1;
        for (int i = h[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                q.push({ dis[v], v });
                pre[v] = u;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (dis[i] >= 1e8) {
            cout << "dist[" << s[0] << "][" << s[i] << "]=" << 256 << endl;
            cout << s[i] << endl;
        }
        else {
            cout << "dist[" << s[0] << "][" << s[i] << "]=" << dis[i] << endl;
            print(i);
            cout << endl;
        }
    }
    return 0;
}

邻接矩阵+朴素dij

#include <iostream>
#include <vector>
#include <algorithm>
#include<stack>
#include<queue>
#include <unordered_map>
#include<string>
#include<cstdio>
#include<map>
using namespace std;
int g[1000][1000], dis[1000], pre[1000], n, m;
bool vis[1000] = { 0 };
string s;
void print(int x) {
    if (pre[x] == -1) {
        cout << s[0];
        return;
    }
    print(pre[x]);
    cout << "->" << s[x];
}
int main() {
    cin >> n >> m;
    cin >> s;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]=1e8;
        }
    }
    for (int i = 0; i < n; i++)dis[i] = 1e8;
    for (int i = 1; i <= m; i++) {
        string a;
        int w;
        cin >> a >> w;
        int j = s.find(a[0]), k = s.find(a[1]);
        g[j][k] = w;
        g[k][j] = w;
    }
    dis[0] = 0, pre[0] = -1;
    for (int i = 1; i <= n - 1; i++) {
        if (g[0][i])dis[i] = g[0][i];
    }
    for (int i = 1; i <= n - 1; i++) {
        int  u = -1;
        for (int j = 1; j <= n - 1; j++) {
            if (!vis[j] && (u == -1 || dis[u] > dis[j])) {
                u = j;
            }
        }
            vis[u] = 1;
            for (int j = 1; j <= n - 1; j++) {
                if (dis[j] >dis[u] + g[u][j]) {
                    pre[j] = u;
                    dis[j] = dis[u] + g[u][j];
                }
            }
    }
    for (int i = 0; i < n; i++) {
        if (dis[i] >= 1e8) {
            cout << "dist[" << s[0] << "][" << s[i] << "]=" << 256 << endl;
            cout << s[i] << endl;
        }
        else {
            cout << "dist[" << s[0] << "][" << s[i] << "]=" << dis[i] << endl;
            print(i);
            cout << endl;
        }
    }
    return 0;
}