欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Cow Relays POJ - 3613(矩阵快速幂+离散化)

程序员文章站 2022-03-16 18:51:04
...

Cow Relays POJ - 3613

For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

Input

  • Line 1: Four space-separated integers: N, T, S, and E
  • Lines 2…T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

Output

  • Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

Sample Input
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

Sample Output
10

题意:

给定一张M条边的无向带权图,点的编号为1~1000,求从起点S到终点E恰好经过K条边的最短路径。保证每个连边的点度至少为2。
2<=M<=100, 2<=K<=1e6

题解:
Cow Relays POJ - 3613(矩阵快速幂+离散化)
Cow Relays POJ - 3613(矩阵快速幂+离散化)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#define ll long long
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 0x3f3f3f3f;

mat mul(const mat &A,const mat &B) {
    mat C(A.size(), vec(B[0].size(), INF));
    for (int i = 0; i < A.size(); i++) {
        for (int k = 0; k < B.size(); k++) {
            for (int j = 0; j < B[0].size(); j++) {
                C[i][j] = min(C[i][j], A[i][k] + B[k][j]);
            }
        }
    }
    return C;
}

mat pow(mat A, int n) {
    //矩阵乘法定义变了,B不能这么初始化
    mat B = A;
    n--;
    while(n > 0) {
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}
int N, T, S, E;

int main() {
    scanf("%d%d%d%d", &N, &T, &S, &E);
    mat A(110, vec(110, INF));
    //离散化
    map<int ,int>mp;
    int cnt = 0;
    for(int i = 0; i < T; i++) {
        int len, u, v;
        scanf("%d%d%d", &len, &u, &v);
        if(mp.count(u) == 0) {
            mp[u] = cnt++;
        }
        u = mp[u];
        if(mp.count(v) == 0) {
            mp[v] = cnt++;
        }
        v = mp[v];
        A[u][v] = min(len, A[u][v]);
        A[v][u] = min(len, A[v][u]);
    }
    A.resize(cnt);
    for(int i = 0; i < A.size(); i++) {
        A[i].resize(cnt);
    }

    A = pow(A, N);
    printf("%d\n", A[mp[S]][mp[E]]);
}
相关标签: 矩阵