本蒟蒻先是写的dijkstra的版本，测了好多遍都是50分，一开始以为是精度问题，就参照了题解的精度，改成了一样的也过不去。最后尝试改成标签中的SPFA就过了，表示很疑惑。

Dijkstra写法（50分）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=10005,M=1e8;
int e[N],w[N],nxt[N],h[N],num=0,dist[N],vis[N][N],f[N],total[N][N];
bool st[N];
int n,m,k,ee;
typedef pair<int,int> PII;
void add(int a,int b,int c)
{
	e[num]=b;
	w[num]=c;
	nxt[num]=h[a];
	h[a]=num++;
}
void dijkstra()
{
	for(int i=1;i<=m;i++) dist[i]=M;
	dist[1]=0;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push(make_pair(1,0));
	while(!q.empty())
	{
		int x=q.top().first;
		q.pop();
		if(st[x]) continue;
		st[x]=true;
		for(int i=h[x];~i;i=nxt[i])
		{
			int j=e[i];
			if(dist[j]>w[i]+dist[x])
			{
				dist[j]=w[i]+dist[x];
				q.push(make_pair(j,dist[j]));
			}
		}
	}
	return;
}
signed main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m>>k>>ee;
	for(int i=1;i<=ee;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	int d;
	cin>>d;
	for(int i=1;i<=d;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		for(int j=y;j<=z;j++) vis[x][j]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			memset(st,0,sizeof st);
			for(int r=i;r<=j;r++)
			{
				for(int k=1;k<=m;k++)
				{
					if(vis[k][r]) st[k]=1;
				}
			}
			dijkstra();
			total[i][j]=dist[m];
		}
	}
	memset(f,0x7f,sizeof f);
	for(int i=1;i<=n;i++)
	{
		f[i]=total[1][i]*i;
		for(int j=i-1;j>=0;j--)
		{
			f[i]=min(f[i],f[j]+total[j+1][i]*(i-j)+k);
		}
	}
	printf("%lld",f[n]);
	return 0;
}

SPFA写法（AC）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=10005,M=1e8;
int e[N],w[N],nxt[N],h[N],num=0,dist[N],vis[N][N],f[N],total[N][N];
bool st[N];
int n,m,k,ee;
typedef pair<int,int> PII;
queue<int> q;
void add(int a,int b,int c)
{
	e[num]=b;
	w[num]=c;
	nxt[num]=h[a];
	h[a]=num++;
}
void SPFA()
{
	for(int i=1;i<=m;i++) dist[i]=M;
	dist[1]=0;
	q.push(1);
	st[1]=true;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		st[u]=false;
		for(int i=h[u];~i;i=nxt[i])
		{
			int v=e[i];
			if(dist[v]>dist[u]+w[i])
			{
				dist[v]=dist[u]+w[i];
				if(!st[v])
				{
					q.push(v);
					st[v]=true;
				}
			}
		}
	}
	return;
}
signed main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m>>k>>ee;
	for(int i=1;i<=ee;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	int d;
	cin>>d;
	for(int i=1;i<=d;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		for(int j=y;j<=z;j++) vis[x][j]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			memset(st,0,sizeof st);
			for(int r=i;r<=j;r++)
			{
				for(int k=1;k<=m;k++)
				{
					if(vis[k][r]) st[k]=1;
				}
			}
			SPFA();
			total[i][j]=dist[m];
		}
	}
	memset(f,0x7f,sizeof f);
	for(int i=1;i<=n;i++)
	{
		f[i]=total[1][i]*i;
		for(int j=i-1;j>=0;j--)
		{
			f[i]=min(f[i],f[j]+total[j+1][i]*(i-j)+k);
		}
	}
	printf("%lld",f[n]);
	return 0;
}

就是最短路写法改了一下

题中数据没有负环，dijkstra却过不了？