首先先读懂题：给你一个有向图，每一条边有一个对应的权值，然后你可以施展k次魔法，把某一条边的权值变为​相反值​。求1到n的最短路径

可以发现，当这一张图是一张有向无环图时，每一条边最多走一遍，所以一开始处理的时候可以全部记录成负数，就可以把这一部分AC了

//Floyd
#include<cmath>
#include<cstdio>
#include<iostream>
const short M(2501),N(101);//比规定值大1即可
const long long I(2500000000001);//无穷大为m*t（边权）+1
long long d[N][N];//d[i][j]表示从i到j的最小距离
int main()
{
	short i,j,l,m,n,u,v;
	int k,t;
	scanf("%hd%hd%d",&n,&m,&k);//输入
	for(i=1; i<=n; ++i)
		for(j=1; j<=n; ++j)
			if(i!=j)//如果i==j，d[i][j]=0
				d[i][j]=I;//否则，赋值成无穷大
	for(i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&u,&v,&t);//输入
		if(k)//能使用魔法
			d[u][v]=-t;//使用魔法
		else//不能使用魔法
			d[u][v]=t;//不使用魔法
	}
	for(l=1; l<=n; ++l)//Floyd板子（加上了一点优化）
		for(i=1; i<=n; ++i)
			if(i!=l)//如果i=l，下面的式子就变成了d[i][j]=min(d[i][j],d[i][i]+d[i][j]),而d[i][i]=0，不用做了
				for(j=1; j<=n; ++j)
					if(i!=j&&j!=l&&d[i][j]>d[i][l]+d[l][j])//同上
						d[i][j]=d[i][l]+d[l][j];
	printf("%lld",d[1][n]);//输出从1到n的最小值
	return 0;
}
//不会有人连题解都没看完就抄走了吧

然而,这只有50分,让我们进一步优化

第一个循环枚举每一条边，第二个循环枚举每一层，循环中第一行表示建立每一层横着的边，第二行表示从上一层到这一层的边

#include<bits/stdc++.h>
using std::queue;
const short K(1001),M(2501),N(101);//比最大值大1即可
const long long I(2500000000001);//无穷大时m*t（边权）+1
//有n*k+n个点，2*m*k+m条边
int c,e[M+2*K*M],h[N+N*K],k,m,n,o[M+2*K*M],w[M+2*K*M];
long long d[N+N*K];
inline void add(int u,int v,int x)
{
	e[++c]=h[u];
	h[u]=c;
	o[c]=v;
	w[c]=x;
}//spfa建边
//spfa模板\注意，这一个spfa不需要bool数组，加上只能得到75分\这一个卡spfa的方式好奇怪
inline void spfa(short s)
{
	int i,u;
	queue<int>q;
	for(i=1; i<=n+n*k; ++i)
		d[i]=I;
	d[s]=0;
	q=queue<int>();
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(i=h[u]; i; i=e[i])
			if(d[o[i]]>d[u]+w[i])
			{
				d[o[i]]=d[u]+w[i];
				q.push(o[i]);
			}
	}
}
int main()
{
	int i,j,u[M],v[M],t[M];
	long long a(I);//要求最小值，先赋值成最大值
	scanf("%d%d%d",&n,&m,&k);//输入
	for(i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&u[i],&v[i],&t[i]);//输入
		add(u[i],v[i],t[i]);//spfa建边
	}
	for(i=1; i<=m; ++i)//建立分层图
		for(j=1; j<=k; ++j)
		{
			add(u[i]+n*j,v[i]+n*j,t[i]);//建立横着的边
			add(u[i]+n*(j-1),v[i]+n*j,-t[i]);//建立斜着的边
		}
	spfa(1);//spfa
	for(i=n; i<=n+n*k; i+=n)
		if(a>d[i])
			a=d[i];//寻找最小值
	printf("%lld",a);
	return 0;
}

这样我们便突破到了90分!

最后利用倍增思想进行收尾

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int max_n=100+5;
const int max_m=2500+5;
int u[max_m],v[max_m],t[max_m];
long long dis[max_n][max_n],d[max_n][max_n];
const long long inf=1e18;
struct Matrix
{
long long v[max_n][max_n];
}A,ans;
inline Matrix operator * (const Matrix &a,const Matrix &b)
{
static Matrix res;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
res.v[i][j]=inf;
for(int k=1;k<=n;++k)
res.v[i][j]=min(res.v[i][j],a.v[i][k]+b.v[k][j]);
}
return res;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=d[i][j]=(i==j?0:inf);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",u+i,v+i,t+i);
dis[u[i]][v[i]]=t[i];
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
ans.v[i][j]=dis[i][j];
for(int k=1;k<=m;++k)
for(int i=1;i<=n;++i)
d[u[k]][i]=min(d[u[k]][i],-t[k]+dis[v[k]][i]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
A.v[i][j]=d[i][j];
while(k)
{
if(k&1)
ans=ans*A;
A=A*A;
k>>=1;
}
printf("%lld\n",ans.v[1][n]);
return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std; 
const int N = 105;
int n, m, p;
ll dis[N][N][3];
struct node{
	ll a[N][N];
	node(){
		memset(a, 0x3f, sizeof(a));
		for (int i = 1; i <= 100; i++) a[i][i] = 0;
	}
	node operator *(const node &x) const{
		node res;
		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					res.a[i][j] = min(a[i][k]+x.a[k][j], res.a[i][j]);
		return res;
	}
}a, ans; 
node qpow(int x){
	while (x){
		if (x&1) ans = ans * a; 
		a = a*a;
		x >>= 1;
	}
}
int main(){
	memset(dis, 0x3f, sizeof(dis));
	cin >> n >> m >> p;
	for (int i=1;i<=n;++i) 
		dis[i][i][0]=dis[i][i][1]=0;
	for (int i = 0; i < m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		dis[u][v][0] = w;
		dis[u][v][1] = -w;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++){
				dis[i][j][0] = min(dis[i][k][0]+dis[k][j][0], dis[i][j][0]);
				dis[i][j][1] = min(min(dis[i][k][0]+dis[k][j][1], dis[i][k][1]+dis[k][j][0]), dis[i][j][1]);
			}
	if (p==0) return cout<<dis[1][n][0],0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a.a[i][j] = dis[i][j][1];
	qpow(p);
	cout << ans.a[1][n];
	return 0;
}