HDU 4725 The Shortest Path in Nya Graph （最短路）

时间：2021-12-25 02:32:11

The Shortest Path in Nya Graph

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

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 <= 105) and C(1 <= C <= 103), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.
The second line has N numbers li (1 <= li <= N), which is the layer of ith node belong to.
Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 104), 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
 
Recommend
zhuyuanchen520
 

最短路。

主要是建图。

N个点，然后有N层，要假如2*N个点。

总共是3*N个点。

点1~N就是对应的实际的点1~N.  要求的就是1到N的最短路。

然后点N+1 ~ 3*N 是N层拆出出来的点。

第i层，入边到N+2*i-1, 出边从N+2*i 出来。（1<= i <= N）

N + 2*i    到  N + 2*(i+1)-1 加边长度为C. 表示从第i层到第j层。

N + 2*(i+1) 到 N + 2*i - 1 加边长度为C,表示第i+1层到第j层。

如果点i属于第u层，那么加边 i -> N + 2*u -1         N + 2*u ->i  长度都为0

然后用优先队列优化的Dijkstra就可以搞出最短路了

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013-9-11 12:30:12

 File Name     :2013-9-11\1010.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 /*

  * 使用优先队列优化Dijkstra算法

  * 复杂度O(ElogE)

  * 注意对vector<Edge>E[MAXN]进行初始化后加边

  */

 const int INF=0x3f3f3f3f;

 const int MAXN=;

 struct qnode

 {

     int v;

     int c;

     qnode(int _v=,int _c=):v(_v),c(_c){}

     bool operator <(const qnode &r)const

     {

         return c>r.c;

     }

 };

 struct Edge

 {

     int v,cost;

     Edge(int _v=,int _cost=):v(_v),cost(_cost){}

 };

 vector<Edge>E[MAXN];

 bool vis[MAXN];

 int dist[MAXN];

 void Dijkstra(int n,int start)//点的编号从1开始

 {

     memset(vis,false,sizeof(vis));

     for(int i=;i<=n;i++)dist[i]=INF;

     priority_queue<qnode>que;

     while(!que.empty())que.pop();

     dist[start]=;

     que.push(qnode(start,));

     qnode tmp;

     while(!que.empty())

     {

         tmp=que.top();

         que.pop();

         int u=tmp.v;

         if(vis[u])continue;

         vis[u]=true;

         for(int i=;i<E[u].size();i++)

         {

             int v=E[tmp.v][i].v;

             int cost=E[u][i].cost;

             if(!vis[v]&&dist[v]>dist[u]+cost)

             {

                 dist[v]=dist[u]+cost;

                 que.push(qnode(v,dist[v]));

             }

         }

     }

 }

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

 {

     E[u].push_back(Edge(v,w));

 }

 int main()

 {

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

     //freopen("out.txt","w",stdout);

     int T;

     int N,M,C;

     scanf("%d",&T);

     int iCase = ;

     while(T--)

     {

         scanf("%d%d%d",&N,&M,&C);

         for(int i = ;i <= *N;i++) E[i].clear();

         int u,v,w;

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

         {

             scanf("%d",&u);

             addedge(i,N + *u - ,);

             addedge(N + *u ,i,);

         }

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

         {

             addedge(N + *i-,N + *(i+),C);

             addedge(N + *(i+)-,N + *i,C);

         }

         while(M--)

         {

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

             addedge(u,v,w);

             addedge(v,u,w);

         }

         Dijkstra(*N,);

         iCase++;

         if(dist[N] == INF)dist[N] = -;

         printf("Case #%d: %d\n",iCase,dist[N]);

     }

     return ;

 }

相关文章