http://acm.hdu.edu.cn/showproblem.php?pid=4725

The Shortest Path in Nya Graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7869 Accepted Submission(s): 1766

Problem Description

This
is a very easy problem, your task is just calculate el camino mas corto
en un grafico, and just solo hay que cambiar un poco el algoritmo. If
you do not understand a word of this paragraph, just move on.
The Nya graph is an undirected graph with "layers". Each node in the graph belongs to a layer, there are N nodes in total.
You
can move from any node in layer x to any node in layer x + 1, with cost
C, since the roads are bi-directional, moving from layer x + 1 to layer
x is also allowed with the same cost.
Besides, there are M extra edges, each connecting a pair of node u and v, with cost w.
Help us calculate the shortest path from node 1 to node N.

Input

The first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has three numbers N, M (0 <= N, M <= 10⁵) and C(1 <= C <= 10³), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.
The second line has N numbers l_i (1 <= l_i <= N), which is the layer of i^th node belong to.
Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 10⁴), which means there is an extra edge, connecting a pair of node u and v, with cost w.

Output

For test case X, output "Case #X: " first, then output the minimum cost moving from node 1 to node N.
If there are no solutions, output -1.

Sample Input

2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3

3 3 3
1 3 2
1 2 2
2 3 2
1 3 4

Sample Output

Case #1: 2
Case #2: 3

Source

一开始无脑暴力建 N1*N2的图，后来超时后才发现，如果层数稀疏，点数密集的话建的边数上亿，肯定要超时的，我们想办法巧妙地建图。

把每一层看做是一个点，通过点->层->点的连接从而实现层与层的连接，可以少建许多边，但我第一次没考虑周到，让点与对应的层建立了双向边，这是致命的，，

因为每一层的点之间距离并非是0，这样构图的话每一层得点相互之间都能0距离显然是错误的。

考虑建单向边，让每一层向层上的点建一条0边，然后对于每个点，向与其相邻且存在的层建立一条权值为C的边，这样就符合了题意。

spfa和dij都写了感觉复杂度差不多，但是第一次建图错误时spfa提示TLE，dij返回WA不知道是否说明dij快点- -反正二者AC的时间差不大多

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 using namespace std;

 #define inf 0x3f3f3f3f

 inline int read()

 {

     int r=;  char c=getchar();

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) {r=r*+c-'';c=getchar();}

     return r;

 }

 struct Edge

 {

     int to,w,next;

 }e[];

 int cnt,first[];

 void add(int u,int v,int w)

 {

     e[cnt].to=v;

     e[cnt].w=w;

     e[cnt].next=first[u];

     first[u]=cnt++;

 }

 struct node

 {

     int u,w;

     bool operator<(const node &x)const{

     return w>x.w;

     }

 };

 int d[];

 int dij(int N)

 {

     bool vis[];

     priority_queue<node>Q;

     memset(vis,,sizeof(vis));

     memset(d,inf,sizeof(d));

     d[]=;

     Q.push(node{,});

     while(!Q.empty()){

         node t1=Q.top();Q.pop();

         int u=t1.u;

         if(vis[u]) continue;

         vis[u]=;

         if(u==N) break;

         for(int i=first[u];i+;i=e[i].next){

             Edge x=e[i];

             if(!vis[x.to]&&d[x.to]>d[u]+x.w){

                 d[x.to]=d[u]+x.w;

                 Q.push(node{x.to,d[x.to]});

             }

         }

     }

     return d[N]==inf?-:d[N];

 }

 int spfa(int N)

 {

     bool vis[];

     queue<int>Q;

     memset(vis,,sizeof(vis));

     memset(d,inf,sizeof(d));

     Q.push();

     vis[]=;

     d[]=;

     while(!Q.empty()){

         int u=Q.front(); Q.pop();

         vis[u]=;

         for(int i=first[u];i+;i=e[i].next){

             Edge x=e[i];

             if(d[x.to]>d[u]+x.w){

                 d[x.to]=d[u]+x.w;

                 if(!vis[x.to]){

                     Q.push(x.to);

                 }

             }

         }

     }

     return d[N]==inf?-:d[N];

 }

 int main()

 {

     //ios::sync_with_stdio(false);

     int T,N,M,C,i,j,k=;

     int u,v,w,x[];

     bool layer[];

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

     T=read();

     for(int cas=;cas<=T;++cas)

     {

         cnt=;

         memset(first,-,sizeof(first));

         memset(layer,,sizeof(layer));

         cin>>N>>M>>C;

         for(i=;i<=N;++i)

         {

             x[i]=read();

             layer[x[i]]=;

         }

        for(i=;i<=N;++i)

         {

             add(x[i]+N,i,);

             add(i,x[i]+N,);

             if(x[i]>&&layer[x[i]-])

                 add(i,x[i]+N-,C);

             if(x[i]<N&&layer[x[i]+])

                 add(i,x[i]+N+,C);

         }

         while(M--){

         scanf("%d%d%d",&u,&v,&w);

             add(u,v,w);

             add(v,u,w);

         }

         printf("Case #%d: %d\n",cas,dij(N)/*spfa(N)*/);

     }

     return ;

 }

巴特西

HDU 4725 建图

The Shortest Path in Nya Graph

最新文章

热门文章