水一发dp+spfa
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cfloat> #include<cctype> #include<cmath> #include<vector> #include<queue> using namespace std; const int maxn=1001, maxm=101, INF=1<<29; int n, m, k, e; //n:days, m:nodes, k:fee, e:number of edges; int p, a, b;//p:point, a:start, b:end; int dp[maxn], cost[maxn][maxn]; int vis[maxn], ban[maxn][maxn], mark[maxn], dis[maxn]; int head[maxn], cnt; struct node{ int to, next, w; }edge[maxm]; void AddEdge(int u, int v, int w) { edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } int spfa(int start, int end) { for(int i=0; i<=m; i++) { dis[i]=INF; vis[i]=0; mark[i]=0; } queue<int> Q; Q.push(1); dis[1]=0; for(int i=start; i<=end; i++) for(int u=1; u<=m; u++) if(ban[u][i]) mark[u]=1; while(!Q.empty()) { int u=Q.front(); vis[u]=false; Q.pop(); for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; int w=edge[i].w; if(!mark[v] && dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!vis[v]) { vis[v]=true; Q.push(v); } } } } return dis[m]*(dis[m]>=INF?1:end-start+1); } int solve() { for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) cost[i][j]=spfa(i, j); for(int i=0; i<=n; i++) dp[i]=INF; dp[0]=-k; for(int i=1; i<=n; i++) for(int j=0; j<i; j++) dp[i]=min(dp[i], dp[j]+cost[j+1][i]+k); printf("%d", dp[n]); } int init() { memset(head, -1, sizeof(head)); scanf("%d%d%d%d", &n, &m, &k, &e); int u, v, w; for(int i=1; i<=e; i++) { scanf("%d%d%d", &u, &v, &w); AddEdge(u, v, w); AddEdge(v, u, w); } scanf("%d", &e); for(int i=1; i<=e; i++) { scanf("%d%d%d", &p, &a, &b); for(int i=a; i<=b; i++) ban[p][i]=1; } } int main() { init(); solve(); return 0; } |