题目： http://61.187.179.132/JudgeOnline/problem.php?id=1003
动规+最短路
先用spfa预处理出c[i][j]表示第i天到第j天走同一条道路的最小花费
然后dp
dp[i]=min(dp[i],dp[j]+c[j+1][i]+k)(1<=i<=n,1<=j<i)
1
#include <iostream>
2#include <cstring>
3#include <cstdio>
4#include <cstdlib>
5using namespace std;
6const int oo=100000001;
7const int MaxN=105;
8const int MaxM=25;
9
10int a[MaxM][MaxM],c[MaxN][MaxN],m,n,k,e,d,dp[MaxN];
11bool f[MaxN][MaxM],ff[MaxM];
12int q[MaxM],dd[MaxM];
13bool v[MaxM];
14
15void init()
16
{
17
memset(a,-1,sizeof(a));
18 memset(f,0,sizeof(f));
19 scanf("%d%d%d%d",&n,&m,&k,&e);
20 for (int i=0;i<e;i++)
21
{
22 int x,y,z;
23 scanf("%d%d%d",&x,&y,&z);
24 if (a[x][y]==-1)
25 {
26 a[x][y]=a[y][x]=z;
27
}
28 else
29 {
30 a[x][y]=a[y][x]=min(a[x][y],z);
31 }
32 }
33 scanf("%d",&d);
34 for (int i=0;i<d;i++)
35 {
36 int x,y,z;
37 scanf("%d%d%d",&x,&y,&z);
38 for (int i=y;i<=z;i++)
39 {
40 f[i][x]=1;
41 }
42 }
43
}
44
45int spfa()
46{
47 q[0]=1;
48 for (int i=1;i<=m;i++)
49 {
50 dd[i]=-1;
51 v[i]=0;
52 }
53 dd[1]=0;
54 v[1]=1;
55 for (int first=0,last=1;first!=last;first++)
56 {
57 if (first>=MaxM)
58 {
59 first-=MaxM;
60 }
61 v[q[first]]=0;
62 for (int i=1;i<=m;i++)
63 {
64 if (a[q[first]][i]!=-1 && ff[i]!=1 && (dd[i]>dd[q[first]]+a[q[first]][i] || dd[i]==-1))
65 {
66 dd[i]=dd[q[first]]+a[q[first]][i];
67 if (v[i]==0)
68 {
69 v[i]=1;
70 q[last++]=i;
71 if (last>=MaxM)
72 {
73 last-=MaxM;
74 }
75 }
76 }
77 }
78 }
79 return dd[m];
80}
81
82void work() //预处理
83{
84 for (int i=1;i<=n;i++)
85 {
86 memcpy(ff,f[i],sizeof(ff));
87 for (int j=i;j<=n;j++)
88 {
89 for (int k=1;k<=m;k++)
90 {
91 ff[k]|=f[j][k];
92 }
93 c[i][j]=spfa()*(j-i+1);
94 }
95 }
96}
97
98int DP()
99{
100 dp[0]=0;
101 for (int i=1;i<=n;i++)
102 {
103 dp[i]=c[1][i];
104 for (int j=0;j<i;j++)
105 {
106 if (c[j+1][i]>0)
107 {
108 if (dp[i]<0)
109 {
110 dp[i]=dp[j]+c[j+1][i]+k;
111 }
112 else
113 {
114 dp[i]=min(dp[i],dp[j]+c[j+1][i]+k);
115 }
116 }
117 }
118 }
119 return dp[n];
120}
121
122int main()
123{
124 init();
125 work();
126 printf("%d\n",DP());
127 return 0;
128}
129