首页 > 代码库 > POJ 3613 Cow Relays
POJ 3613 Cow Relays
Cow Relays
64-bit integer IO format: %lld Java class name: Main
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 411 4 64 4 88 4 96 6 82 6 93 8 9
Sample Output
10
Source
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 int lisan[2010],n = 0,k,t,s,e;18 struct Matrix {19 int m[210][210];20 Matrix() {21 for(int i = 0; i < 210; i++)22 for(int j = 0; j < 210; j++)23 m[i][j] = INF;24 }25 };26 Matrix mul(Matrix &x,Matrix &y) {27 Matrix z;28 for(int k = 1; k <= n; k++){29 for(int i = 1; i <= n; i++){30 for(int j = 1; j <= n; j++)31 z.m[i][j] = min(z.m[i][j],x.m[i][k]+y.m[k][j]);32 }33 }34 return z;35 }36 Matrix fastPow(Matrix x,int index){37 Matrix y;38 for(int i = 0; i <= n; i++) y.m[i][i] = 0;39 while(index){40 if(index&1) y = mul(y,x);41 index >>= 1;42 x = mul(x,x);43 }44 return y;45 }46 int main() {47 Matrix now;48 int w,u,v;49 scanf("%d %d %d %d",&k,&t,&s,&e);50 while(t--){51 scanf("%d %d %d",&w,&u,&v);52 if(!lisan[u]) lisan[u] = ++n;53 if(!lisan[v]) lisan[v] = ++n;54 now.m[lisan[u]][lisan[v]] = now.m[lisan[v]][lisan[u]] = w;55 }56 now = fastPow(now,k);57 printf("%d\n",now.m[lisan[s]][lisan[e]]);58 return 0;59 }
POJ 3613 Cow Relays