C++(g++ 7.5.0) 解法, 执行用时: 41ms, 内存消耗: 564K, 提交时间: 2023-04-25 15:05:21

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1010,M = 110,INF=  0x3f3f3f3f;
int n,t,s,e,idx;
int g[M][M],mp[M][M],h[N];
void mul(int f[][M],int a[][M])
{
    int res[M][M];
    memset(res,INF,sizeof res);
    for(int k=1;k<=idx;k++)
      for(int i=1;i<=idx;i++)
        for(int j=1;j<=idx;j++)
          res[i][j] = min(res[i][j],f[i][k]+a[k][j]);
    memcpy(f,res,sizeof res);
}
int main()
{
    scanf("%d%d%d%d",&n,&t,&s,&e);
    memset(g,INF,sizeof g);
    while(t--)
    {
        int u,v,w; scanf("%d%d%d",&w,&u,&v);
        if(!h[u]) h[u] = ++idx;
        if(!h[v]) h[v] = ++idx;
        g[h[u]][h[v]] = min(g[h[u]][h[v]],w);
        g[h[v]][h[u]] = g[h[u]][h[v]];
    }
    memcpy(mp,g,sizeof g);
    n--;
    while(n)
    {
        if(n&1) mul(g,mp);
        mul(mp,mp);
        n>>=1;
    }
    printf("%d\n",g[h[s]][h[e]]);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 56ms, 内存消耗: 1144K, 提交时间: 2020-02-20 20:57:30

#include <bits/stdc++.h>
using namespace std;
int K, n, m, s, t, x, y, z;
map<int, int> mp;
struct Matrix {
	int a[205][205];
	Matrix operator * (Matrix &r) {
		Matrix c;
		memset(c.a, 0x3f, sizeof c.a);
		for(int i = 1; i <= n; i++)	for(int j = 1; j <= n; j++)	for(int k = 1; k <= n; k++)	c.a[i][j] = min(c.a[i][j], a[i][k] + r.a[k][j]);
		return c;
	}
} st, ans;
void power() {
	ans = st, K--;
	while(K) {
		if(K & 1) ans = ans * st;
		st = st * st;
		K >>= 1;
	}
}
int main() {
	scanf("%d%d%d%d", &K, &m, &s, &t);
	memset(st.a, 0x3f, sizeof st.a);
	while(m--) {
		scanf("%d%d%d", &z, &x, &y);
		if(mp[x]) x = mp[x];
		else x = mp[x] = ++n;
		if(mp[y]) y = mp[y];
		else y = mp[y] = ++n;
		st.a[x][y] = st.a[y][x] = z;
	}
	power();
	printf("%d", ans.a[mp[s]][mp[t]]);
	return 0;
}

C++ 解法, 执行用时: 16ms, 内存消耗: 932K, 提交时间: 2022-01-13 14:45:32

#include<bits/stdc++.h> 
using namespace std;
int hs[1001],n,k,q,z,tn,x,y,w;
struct nd{
    int a[201][201];
    nd operator *(const nd &x)const{
        nd c;
        memset(c.a,0x3f,sizeof(c.a));
        for(int k=1;k<=tn;k++)for(int i=1;i<=tn;i++)for(int j=1;j<=tn;j++)c.a[i][j]=min(c.a[i][j],a[i][k]+x.a[k][j]);
        return c;
     }
}s,ans;
int main(){
	cin>>k>>n>>q>>z;
    memset(s.a,0x3f,sizeof(s.a));
    for(int i=1;i<=n;i++){cin>>w>>x>>y;if(!hs[x])hs[x]=++tn;if(!hs[y])hs[y]=++tn;s.a[hs[x]][hs[y]]=s.a[hs[y]][hs[x]]=w;}
    ans=s;
	k--;
	for(;k;k>>=1){if(k&1)ans=ans*s;s=s*s;}
    cout<<ans.a[hs[q]][hs[z]];
    return 0;
}