[UVA10246] 巧妙优化 最短路 打表

【题目来源】http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1187

看不到的请用firefox浏览器。

【题目大意】给出一个无向图,点有点权,边有边权。然后有Q个询问(X,Y),表示求一条从X到Y的路径,其总代价为路上边权只和加上路径上点权最大的一个点的点权。询问就使这个总代价最少是多少?

【算法分析】

翻开《算法艺术与信息学竞赛》第308页就有这个题目。

我们假定了K为点权最大的点,那么显然,对于询问(X,Y):W=D[X,K]+D[K,Y]+COST[K]。

其中D[X,K]和D[K,Y]表示删除权值比K大的点以后的最短路。

由于是无向图,再转变一下。

W=D[K,X]+D[K,Y]+COST[K]。

到了这一步。。。大家都知道怎么打表了吧。。。

我们就先预处理出D[i,j]表示从第i个出发,且所有点权>COST[i]的点都已删掉以后,到达j的最短路。

这可以用SPFA实现,复杂度O(NM)

然后打表,复杂度O(N^3)

【其他】我居然WA了4次,因为同一个问题:我把Case #xxx看成是题目给的方便你看的。。。没有输出。。。我那叫一个纠结吖~拿块豆腐撞死自己算了

【code】

#include #include #include #include #define INF 0x7FFFFFFF
#define E 1000000
#define N 1000
using namespace std;
struct gtp{int x,y,w,next;}g[E];
int n,m,q,e,ls[N],ans[N][N],Vp[N],dist[N][N];
int d[N],list[N],v[N];

void add(int x,int y,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}

void init(){
    memset(ls,0,sizeof(ls));
    for (int i=1;i<=n;i++) scanf("%d",&Vp[i]);
    e=0;
    for (int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
}

void spfa(int st){
    int head=0,tail=1; list[1]=st;
    memset(v,0,sizeof(v));
    for (int i=1;i<=n;i++) d[i]=INF;
    d[st]=0; v[st]=1;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (int t=ls[list[head]];t!=0;t=g[t].next)
          if (Vp[g[t].y]<=Vp[st] && d[g[t].x]+g[t].w              d[g[t].y]=d[g[t].x]+g[t].w;
              if (v[g[t].y]==0){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }
        }
        v[list[head]]=0;
    }
}

void work(){
    for (int i=1;i<=n;i++){
        spfa(i);
        for (int j=1;j<=n;j++) dist[i][j]=d[j];
    }
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        ans[i][j]=INF;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        for (int k=1;k<=n;k++){
          int tmp;
          if (dist[k][i]==INF || dist[k][j]==INF) tmp=INF;
          else tmp=dist[k][i]+dist[k][j]+Vp[k];
          ans[i][j]=min(ans[i][j],tmp);
        }
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        if (ans[i][j]==INF) ans[i][j]=-1;
}

void print(){
    for (int i=1;i<=q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%dn",ans[x][y]);
    }
}

int main(){
    int test=0;
    for (;;){
        scanf("%d%d%d",&n,&m,&q);
        if (n+m+q==0) break;
        test++;
        if (test>1) printf("n");
        init();
        work();
        printf("Case #%dn",test);
        print();
    }
    return 0;
}

留下评论

您的电子邮箱地址不会被公开。