#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct node
{
int v,z,d,next;//存可以连接的点，用next存邻接表
}a[10010];
struct road
{
int u,cnt,dis;//dis储存当前需要的钱数，即最短路算法里的权，u储存顶点，cnt储存组合数即状态压缩dp
road(int uu,int cntt,int diss)
{
u=uu;
cnt=cntt;
dis=diss;
}
bool operator < (const road &x)const
{
return dis>x.dis;//将费用小的放在前面
}
};
int first[110],co1[110],co2[110],employ[10],d[110][20000],re[10];//re储存传话人物的使用次数
int n,m,cc,len;
void bellman_ford()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<employ[m];j++)
{
d[i][j]=inf;//初始化
}
}
d[0][0]=0;
priority_queue<road>q;
q.push(road(0,0,0));
while(!q.empty())
{
road qq=q.top();
q.pop();
if(qq.dis>d[qq.u][qq.cnt])//已经是更优的解，无需松弛
continue;
if(qq.u==n-1)//松弛到达n-1
{
printf("%d
",qq.dis);
return;
}
for(int i=first[qq.u];i!=-1;i=a[i].next)//搜寻邻接表
{
int tmp=qq.cnt;
for(int j=0;j<m;j++)//更新每一个employee在这条路上的使用次数
{
re[j]=tmp%3;
tmp/=3;
}
int v=a[i].v;
int z=a[i].z;
int cost=a[i].d;
int t=1;
if(re[z]==1)
{
cost+=co1[z];
}
else if(re[z]==2)
{
cost+=co2[z];
t=0;
}
if(d[v][qq.cnt+t*employ[z]]>qq.dis+cost)//最短路算法的核心
{
d[v][qq.cnt+t*employ[z]]=qq.dis+cost;
q.push(road(v,qq.cnt+t*employ[z],d[v][qq.cnt+t*employ[z]]));
}
}
}
printf("-1
");
}
void add_edge(int u,int v,int z,int d)
{
a[len].v=v;
a[len].z=z;
a[len].d=d;
a[len].next=first[u];
first[u]=len++;
}
int main()
{
employ[0]=1;
for(int i=1;i<=9;i++)
{
employ[i]=3*employ[i-1];//初始化
}
while(~scanf("%d%d%d",&n,&m,&cc))
{
memset(first,-1,sizeof(first));
for(int i=0;i<m;i++)
{
scanf("%d",&co1[i]);
}
for(int i=0;i<m;i++)
{
scanf("%d",&co2[i]);
}
len=0;
int x,y,z,d;
for(int i=0;i<cc;i++)
{
scanf("%d%d%d%d",&x,&y,&z,&d);
add_edge(x,y,z,d);
}
bellman_ford();//可以求负权的最短路算法
}
return 0;
}
//思路仍待跟进
bellman的核心代码只有4行
for(int k=1;k<=n-1;k++)//进行n-1次松弛
for(int i=1;i<=m;i++)//枚举每一条边
if(dis[v[i]]>dis[u[i]]+w[i])//尝试松弛每一条边
dis[v[i]]=dis[u[i]]+w[i];
这个算法也是遍历n-1遍找过所有的点，至于为什么是n-1呢。dijs算法n-1次遍历是因为有n-1个点需要遍历，这个也是因为最短路是一个不包含回路的路径，无论正负权回路都不能有，那么去掉回路，n个点任意两点之间就最多有n-1条边。但是程序可能在不到n-1次循环就已经找到了所有最短路，说明这个是最坏情况下是n-1次遍历。
dis同样是存在起始点到各个顶点的最短路，这个与dijs不同的是，dijs每次找到最近的点进行松弛操作，而这个bellman则是只要路程更短我就松弛。也是因为这样才能用来解决负权值问题。
那么怎么来看有负权值回路呢，如果有负权值回路，那最短路就不会存在，因为最短路会越来与小。那么在n-1轮松弛后，要是还能松弛就代表有负权值回路。