poj 3613(最短路)

题意：求解经过不多于某边数的最短路

思路：矩阵连乘，乘的次数就是不多于某边数的最短路，题目给出的顶点需要映射处理

View Code

 1 #include<iostream>
 2 #include<map>
 3 #include<stdio.h>
 4 #include<string.h>
 5 using namespace std;
 6 #define N 202
 7 struct matrix{
 8     int f[N][N];
 9     matrix(){
10         memset(f,0x3f,sizeof(f));
11     }
12 };
13 int num;
14 matrix mul(matrix a,matrix b)
15 {
16     matrix c;
17     for(int i=1;i<=num;i++)
18     for(int j=1;j<=num;j++)
19     for(int k=1;k<=num;k++)
20     {
21         c.f[i][j]=min(c.f[i][j],a.f[i][k]+b.f[k][j]);
22     }
23     return c;
24 }
25 matrix pow(matrix m,int n)
26 {
27     if(n==1)return m;
28     matrix tmp=pow(m,n/2);
29     if(n&1)return mul(mul(tmp,tmp),m);
30     return mul(tmp,tmp);
31 }
32 map<int,int> mp;
33 int main()
34 {
35     int n,t,s,e;
36     num=0;
37     scanf("%d%d%d%d",&n,&t,&s,&e);
38     mp.clear();
39     matrix c;
40     for(int i=1;i<=t;i++)
41     {
42         int a,b,w;
43         scanf("%d%d%d",&w,&a,&b);
44         if(mp[a]==0)mp[a]=++num;
45         if(mp[b]==0)mp[b]=++num;
46         c.f[mp[a]][mp[b]]=c.f[mp[b]][mp[a]]=w;
47     }
48     pow(c,1);
49     matrix out=pow(c,n);
50     cout<<out.f[mp[s]][mp[e]]<<endl;
51     return 0;
52 }