POJ3613 Cow Relays [矩阵乘法 floyd类似]

时间：2022-12-25 05:23:43
Cow Relays
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 7335   Accepted: 2878

Description

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

Source

b在大很多也可以
求经过b条边的最短路
貌似直接想floyd不太明白了，一遍floyd怎么是经过一条边的最短路呢？
还是从矩阵乘法考虑，构造一个向量表示距离，不停乘邻接矩阵
定义一种新矩阵乘法，不是加起来而是求最小值
 
初始化时用0x3f
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int b,n,m,s,t,u,v,w;

int mp[];

struct Mat{

    int a[N][N];

    Mat(){memset(a,0x3f,sizeof(a));}

}G,ans;

Mat operator *(Mat A,Mat B){

    Mat C;

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++) if(A.a[i][k])

            for(int j=;j<=n;j++) if(B.a[k][j])

                C.a[i][j]=min(C.a[i][j],A.a[i][k]+B.a[k][j]);

    return C;

}

int main(){

    //freopen("in.txt","r",stdin);

    b=read();m=read();s=read();t=read();

    if(!mp[s]) mp[s]=++n;s=mp[s];

    if(!mp[t]) mp[t]=++n;t=mp[t];

    for(int i=;i<=m;i++){

        w=read();u=read();v=read();

        if(!mp[u]) mp[u]=++n;u=mp[u];

        if(!mp[v]) mp[v]=++n;v=mp[v];

        G.a[u][v]=G.a[v][u]=w;

    }

    ans=G;b--;

    for(;b;b>>=,G=G*G)

        if(b&) ans=ans*G;

    printf("%d",ans.a[s][t]);

}
 
 

相关文章