| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions:9207 | Accepted: 3604 |
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
题意：
在一个图上求从$S$到$E$的，刚好经过$n$条边的最短路径长。
思路：
没想到最短路的题目还可以用快速幂。也没想到快速幂还可以这么写。
这道题边最多是100条，所以可以先把点离散化。离散化后点的编号最大是$node_cnt$
最初的矩阵$G[i,j]$中存储的其实是从$i$经过一条边到达$j$的最短路
那么$G^{(2)}[i, j] = \min_{1\leq k\leq node_cnt}{G[i, k] + G[k, j]}$就可以表示从$i$经过两条边到达$j$的最短路
如果矩阵$G^{(m)}$表示任意两点之间恰好经过$m$条边的最短路，那么
$G^{(r+m)}[i, j] = \min_{1\leq k\leq node_cnt}{G^{(r)}[i, k] + G^{(m)}[k, j]}$
这就可以使用快速幂进行递推了。只需要把$matrix$的乘法操作中，$+=$变成$\min$, $*$变成$+$
注意矩阵要初始化为$+\infty$
#include<iostream>
//#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<climits>
#include<map>
using namespace std;
typedef long long LL;
#define N 100010
#define pi 3.1415926535
#define inf 0x3f3f3f3f int n, t, S, E;
const int maxn = ;
int node_cnt;
struct matrix{
int m[maxn][maxn];
//int m_size;
matrix operator *(const matrix &b)const{
matrix ret;
memset(ret.m, 0x3f, sizeof(ret.m));
for(int i = ; i <= node_cnt; i++){
for(int j = ; j <= node_cnt; j++){
//ret.m[i][j] = inf;
for(int k = ; k <= node_cnt; k++){
ret.m[i][j] = min(m[i][k] + b.m[k][j], ret.m[i][j]);
}
}
}
return ret;
}
}g;
//int g[maxn][maxn];
struct edge{
int u, v, length;
}e[];
set<int>nodes;
set<int>::iterator set_it;
map<int, int>node_mp; matrix ksm(matrix a, int x)
{
matrix ret, k;
k = a;
ret = a;
x--;
while(x){
if(x & ){
ret = ret * k;
}
x >>= ;
k = k * k;
}
return ret;
} int main()
{
while(scanf("%d%d%d%d", &n, &t, &S, &E) != EOF){
for(int i = ; i < t; i++){
scanf("%d%d%d", &e[i].length, &e[i].u, &e[i].v);
nodes.insert(e[i].u);
nodes.insert(e[i].v);
} node_cnt = ;
for(set_it = nodes.begin(); set_it != nodes.end(); set_it++){
node_mp[*set_it] = ++node_cnt;
}
//g.m_size = node_cnt;
memset(g.m, 0x3f, sizeof(g.m));
for(int i = ; i < t; i++){
int u = e[i].u, v = e[i].v;
g.m[node_mp[u]][node_mp[v]] = e[i].length;
g.m[node_mp[v]][node_mp[u]] = e[i].length;
}
/*for(int i = 1; i <= node_cnt; i++){
for(int j = 1; j <= node_cnt; j++){
cout<<g.m[i][j]<<" ";
}
cout<<endl;
}*/ matrix ans = ksm(g, n);
//cout<<node_mp[S]<<" "<<node_mp[E]<<endl;
printf("%d\n", ans.m[node_mp[S]][node_mp[E]]);
}
return ;
}