The Shortest Path in Nya Graph HDU - 4725

发布时间：2020-12-14 05:08:14 所属栏目：大数据来源：网络整理

导读：题目： 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 undir

题目：

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.

InputThe 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.OutputFor 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

Sample Output

Case #1: 2
Case #2: 3

分析：
主要是构图，m条边正常建，对于相邻层的建图：对于每一层，层点 → 该层每个点，该层每个点→邻层层点（均为单项）
代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 9e5 + 10;
 5 const ll inf = 1e18;
 6 struct edge
 7 {
 8     int e,v,next;
 9     edge(int a = 0,int b = 0,int c = 0) : e(a),v(b),next(c) {}
10 }e[maxn];
11 int head[maxn];
12 ll dis[maxn];
13 int vis[maxn];
14 int v[maxn];
15 int have[maxn];
16 int tot;
17 
18 struct node
19 {
20     int e;
21     ll dis;
22     node(int a = 0,ll b = 0) : e(a),dis(b) {}
23     bool operator< (const node& a) const
24     {
25         return a.dis < dis;
26     }
27 };
28 
29 void add(int x,int y,int v,int tot)
30 {
31     e[tot] = edge(y,head[x]);
32     head[x] =tot;
33 }
34 
35 void dj()
36 {
37     for (int i = 1; i < maxn; i++)
38         dis[i] = inf;
39     dis[1] = 0;
40     memset(vis,0,sizeof(vis));
41     priority_queue<node> q;
42     q.push(node(1,0));
43 
44 
45     while (!q.empty())
46     {
47         node temp = q.top(); q.pop();
48         int u = temp.e;
49         if (vis[u]) continue;
50         vis[u] = 1;
51         for (int i = head[u]; i != -1; i = e[i].next)
52         {
53             int y = e[i].e;
54             if (!vis[y] && dis[y] > dis[u] + e[i].v)
55             {
56                 dis[y] = dis[u] + e[i].v;
57                 q.push(node(y,dis[y]));
58             }
59         }
60     }
61 }
62 
63 int main()
64 {
65     int T; cin >> T;
66     int n,m,c;
67     int cases = 0;
68 
69     while (T--)
70     {
71         int x,y,w;
72 
73         cin >> n >> m >> c;
74         tot = 0;
75         memset(head,-1,sizeof(head));
76         memset(have,sizeof(have));
77         for (int i = 1; i <= n; i++)//input
78         {
79             scanf("%d",&v[i]);
80             have[v[i]] = 1;
81         }
82         for (int i = 1; i <= n; i++)
83         {
84             add(v[i] + n,i,++tot);
85             if (v[i] > 1 && have[v[i] - 1]) add(i,v[i] - 1 + n,c,++tot);
86             if (v[i] < n && have[v[i] + 1]) add(i,v[i] + 1 + n,++tot);
87         }
88         for (int i = 1; i <= m; i++)//point to point
89         {
90             scanf("%d%d%d",&x,&y,&w);
91             add(x,w,++tot);
92             add(y,x,++tot);
93         }
94         dj();
95         printf("Case #%d: %lldn",++cases,dis[n] == inf ? -1 : dis[n]);
96     }
97 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!