标题效果：给定一个无向图。输送n日，有一天的某一时刻不能去，更换行考虑k，求总成本

一阶cost[i][j]用于第一i为了天j天正在同一航线的最低消费 这种利用SPFA处理

然后就是移动的法规问题 订购f[i]至1~i最低消费天

然后，f[i]=min{ f[j]+cost[j+1][i]+k } ( 0<=j<i )

注意m和n别写反

乘天数之前要特判是不是正无穷

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

struct abcd{

	int to,f,next;

}table[10000];

int head[30],tot;

int n,m,_k,e,d,cost[110][110];

bool ban[30][110],unusable[30];

int q[65540],f[110],v[30];

unsigned r,h;

void SPFA()

{

	int i;

	memset(f,0x3f,sizeof f);

	q[++r]=1;f[1]=0;

	while(r!=h)

	{

		int x=q[++h];

		v[x]=0;

		for(i=head[x];i;i=table[i].next)

			if(!unusable[table[i].to])

				if(f[x]+table[i].f<f[table[i].to])

				{

					f[table[i].to]=f[x]+table[i].f;

					if(!v[table[i].to])

						v[table[i].to]=1,q[++r]=table[i].to;

				}

	}

}

void Add(int x,int y,int z)

{

	table[++tot].to=y;

	table[tot].f=z;

	table[tot].next=head[x];

	head[x]=tot;

}

int main()

{

	int i,j,k,x,y,z;

	cin>>n>>m>>_k>>e;

	for(i=1;i<=e;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		Add(x,y,z);

		Add(y,x,z);

	}

	cin>>d;

	for(i=1;i<=d;i++)

	{

		scanf("%d%d%d",&z,&x,&y);

		for(j=x;j<=y;j++)

			ban[z][j]=1;

	}

	for(i=1;i<=n;i++)

		for(j=i;j<=n;j++)

		{

			memset(unusable,0,sizeof unusable);

			for(x=2;x<m;x++)

				for(k=i;k<=j;k++)

					if(ban[x][k])

					{

						unusable[x]=1;

						break;

					}

			SPFA();

			cost[i][j]=f[m]*(f[m]>=0x3f3f3f3f?

1:j-i+1);

		}

	memset(f,0x3f,sizeof f);

	f[0]=0;

	for(i=1;i<=n;i++)

		for(j=0;j<i;j++)

			f[i]=min(f[i],f[j]+cost[j+1][i]+_k);

	cout<<f[n]-_k<<endl;

}