牛站

标签：temp idx int res 牛站 ids ++

// 牛站.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using  namespace std;

/*
https://www.acwing.com/problem/content/347/
给定一张由 T 条边构成的无向图，点的编号为 1∼1000 之间的整数。
求从起点 S 到终点 E 恰好经过 N 条边（可以重复经过）的最短路。
注意: 数据保证一定有解。

输入格式
第 1 行：包含四个整数 N，T，S，E。
第 2..T+1 行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

输出格式
输出一个整数，表示最短路的长度。

数据范围
2≤T≤100,
2≤N≤106
输入样例：
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
输出样例：
10
*/

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>

using namespace std;


const int N = 105;
int g[N][N];
int res[N][N];
map<int, int> ids;
int idx;

int n, t, s, e;

void mul(int c[][N], int a[][N], int b[][N]) {
    static int temp[N][N];
    memset(temp, 0x3f, sizeof temp);

    for (int k = 0; k < idx; k++)
        for (int i = 0; i < idx; i++)
            for (int j = 0; j < idx; j++) {
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
            }

    memcpy(c, temp, sizeof temp);
}


void solve() {
    memset(res, 0x3f, sizeof res);
    for (int i = 0; i < idx; i++) res[i][i] = 0;
    while (n) {
        if (n & 1) mul(res, res, g);
        mul(g, g, g);
        n >>= 1;
    }
}

int main()
{
    cin >> n >> t >> s >> e;
    ids[s] = idx++;
    ids[e] = idx++;
    s = ids[s]; e = ids[e];
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < t; i++) {
        int c, a, b; cin >> c >> a >> b;
        if (ids.count(a) == 0) {
            ids[a] = idx++;
        }
        if (ids.count(b) == 0) {
            ids[b] = idx++;
        }
        g[ids[a]][ids[b]] = min(g[ids[a]][ids[b]],c);
        g[ids[b]][ids[a]] = min(g[ids[b]][ids[a]], c);
    }

    solve();
    cout << res[s][e] << endl;
    return 0;
}

标签：temp,idx,int,res,牛站,ids,++
From： https://www.cnblogs.com/itdef/p/18335266