K - The Shortest Path in Nya Graph
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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.
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 5) and C(1 <= C <= 10 3), 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 4), which means there is an extra edge, connecting a pair of node u and v, with cost w.
For each test case, first line has three numbers N, M (0 <= N, M <= 10 5) and C(1 <= C <= 10 3), 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 4), 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.
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
初解:刚开始看到这题,好像和B题差不多嘛。没想到敲的代码竟然不对。然后又仔细看子题意,说是相邻层可以用C到达,然后就改了还是不对。看来还是题意不理解啊。把这题目的英语都翻译得自己都全懂了,可是为啥还是不对呢。无语死了……无奈看了别人的题解。原来点与点、层与层之间都得入边……唉……还是自己太嫩了……这种建图以前没有遇到过,搞得现在一头雾水滴!!隐含的建图方式自己还是不会,虽然看别人的题解看懂了,但是这种构图方式看来得多练练了!
思路:
1、对于每个点.向其层的出点做边.距离为0..其层的入点向其做边.距离为0....规定n+2*i为第i层入点,n+2*(i+1)是第i层出点
2、对于每一层..其出点向其相邻层做边.距离为C..
3、根据题目所给的另外m段...两两间做边...
这样所构的图就可以在线性时间内完成最短路的查找了。
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <list> #include <queue> #include <string> #include <cstring> #include <map> #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define pri(a) printf("%d\n",a) #define M 1000002 #define INF 168430090 using namespace std; typedef long long ll; int n,m,c,i,u,v,w,tot,ans=INF,head[M],dist[M],vis[M]; struct node { int v,w; bool operator < (const struct node a)const { return a.w < w; //自定义比较函数 } }s,x,y; struct edge { int u,v,w,next; } e[M]; void add(int u,int v,int w) { e[tot].u = u; e[tot].v = v; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++; } int dijkstra() { priority_queue<node>q; mem(vis,0); mem(dist,-1); //也可以初始化为无穷大,最后判断-1情况就得了 s.v = 1; dist[1]=s.w = 0; q.push(s); while(!q.empty()) { x = q.top(); q.pop(); u = x.v; if(vis[u]) continue; vis[u]=1; for(i=head[u]; i!=-1; i=e[i].next) { v = e[i].v; w = e[i].w; if(dist[v]==-1||dist[v]>dist[u]+w) { dist[v]=dist[u]+w; y.v=v; y.w=dist[v]; q.push(y); } } } return dist[n]; } int main() { int t,k,a; sca(t); for(k=1;k<=t;k++) { mem(head,-1); tot = 0; scanf("%d%d%d",&n,&m,&c); for(i=1;i<=n;i++) { sca(a); //结点入边好难 add(i,n+2*a,0); add(n+2*a+1,i,0); } for(i=1;i<=n;i++) { //层之间入边也挺难的 add(n+2*i,n+2*(i+1)+1,c); add(n+2*(i+1),n+2*i+1,c); } for(i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } printf("Case #%d: %d\n",k,dijkstra()); } return 0; }
CUGB图论专场:K - The Shortest Path in Nya Graph(dijkstra优先队列优化+线性构图入边)