(中等) HDU 4725 The Shortest Path in Nya Graph，Dijkstra+加点。-白红宇

(中等) HDU 4725 The Shortest Path in Nya Graph，Dijkstra+加点。

阅读量：4577 次

发布时间：2019-06-08

本文共 2539 字，大约阅读时间需要 8 分钟。

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.

　　题意就是求最短路问题，但是有一个层的概念，刚开始的时候是想着把相邻两层之间的每一点都再连一条边，但是这样的复杂度可以到达 n^2 ，比如在相邻两层上都有 n/2 个点。

　　然后百度了之后，发现是要增加点，表示每一层，这个点和同层的连边的边权为0，这样的话两层之间就只需要再加一条边，但是这样还有一个问题，就是同层点之间来往的话，应该是到达相邻的层然后再回来，所以需要在每一层增加两点，分别表示入的和出的。。。

　　还有一个坑点，就是如果某一层没有点的话，是不能与相邻层连线的。。。

代码如下：

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                      using namespace std;const int MaxN=100005*10;const int MaxM=100005*10;const int INF=10e9+7;struct Edge{ int to,next,cost;};struct Node{ int v,val; Node(int _v=0,int _val=0):v(_v),val(_val) {} bool operator < (const Node &a) const { return val>a.val; }};Edge E[MaxM];int head[MaxN],Ecou;void init(int N){ Ecou=0; for(int i=1;i<=N;++i) head[i]=-1;}void addEdge(int u,int v,int c){ E[Ecou].to=v; E[Ecou].cost=c; E[Ecou].next=head[u]; head[u]=Ecou++;}bool vis[MaxN];void Dijkstra(int lowcost[],int N,int start){ priority_queue 
                     
                       que; Node temp; int u,v,c; int len; for(int i=1;i<=N;++i) { lowcost[i]=INF; vis[i]=0; } lowcost[start]=0; que.push(Node(start,0)); while(!que.empty()) { temp=que.top(); que.pop(); u=temp.v; if(vis[u]) continue; vis[u]=1; for(int i=head[u];i!=-1;i=E[i].next) { v=E[i].to; c=E[i].cost; if(!vis[v] && lowcost[v]> lowcost[u]+c) { lowcost[v]=lowcost[u]+c; que.push(Node(v,lowcost[v])); } } }}int ans[MaxN];bool have[MaxN];int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T; int N,M,C; int u,v,c; int cas=1; scanf("%d",&T); while(T--) { scanf("%d %d %d",&N,&M,&C); init(3*N); memset(have,0,sizeof(have)); for(int i=1;i<=N;++i) { scanf("%d",&u); addEdge(i,N+2*u-1,0); addEdge(N+2*u,i,0); have[u]=1; } for(int i=1;i

View Code

转载于:https://www.cnblogs.com/whywhy/p/4338413.html

你可能感兴趣的文章