RMQ-ST < txia

水一发dp+spfa

#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;
}

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;

}

txia

Tag Archives: 算法笔记

RMQ-ST

[BZOJ1003] 物流运输

Home > 算法笔记

Search