The Shortest Path in Nya Graph
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
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
题意：有n个点，m条通路，每个点到相邻的层需要w权值，告诉每个点所在的层数，每条通路连接的点及权值，1到n点的最小权值。
题解：最短路问题，因为数据量问题所以用dijstral算法+优先队列。
- 难点在于如何解决每个点到相邻的通路解决问题，注意如果这一层没有点是不用考虑的。
我在每一个点加了一个对应的虚拟点，其他相邻的层的点到虚拟点的距离为w，虚拟点到这个点的距离为0，这样就实现了相邻层到达的问题。
另外这个题目数组大小问题，因为加了点的问题，建议点的数目是题目给的两倍以上，路的数目是题目给的五倍以上。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int INF = 1e9+7;
const int maxn = 500050;
struct node
{
int u,w;
node(int a,int b):u(a),w(b){}
bool operator <(const node &q)const
{
return w>q.w;
}
};
struct edge
{
int to,w,next;
}s[maxn];
int num,head[maxn],m,n;
int f[maxn],a[maxn],dis[maxn];
void add(int u,int v,int w)
{
s[num].to = v;
s[num].w = w;
s[num].next = head[u];
head[u] = num++;
}
void dij()
{
priority_queue<node> q;
memset(f,0,sizeof(f));
int i,u,v,w;
for(i=0;i<=2*n;i++)
dis[i] = INF;
dis[1] = 0;
q.push(node(1,0));
while(!q.empty())
{
node t1 = q.top();
q.pop();
u = t1.u;
if(f[u])
continue;
f[u] = 1;
for(i=head[u];i!=-1;i=s[i].next)
{
v = s[i].to;
w = s[i].w;
if(f[v])
continue;
if(dis[u]+w<dis[v])
{
dis[v] = dis[u] + w;
q.push(node(v,dis[v]));
}
}
}
if(dis[n]==INF)
printf("-1\n");
else
printf("%d\n",dis[n]);
}
int main()
{
int t,i,k=1,u,v,w,x;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&x);
memset(head,-1,sizeof(head));
memset(f,0,sizeof(f));
num = 0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[a[i]] = 1;
}
for(i=1;i<=n;i++)
{
if(a[i]==1)/*如果是第一层的话只要链接上一层就可以了*/
{
add(a[i]+n,i,0);
if(f[a[i]+1]&&a[i]<n)
add(i,a[i]+n+1,x);
}
else if(a[i]==n)/*如果是第n层的话只要链接下一层就可以了*/
{
add(a[i]+n,i,0);
if(f[a[i]-1]&&a[i]>1)
add(i,a[i]+n-1,x);
}
else
{
add(a[i]+n,i,0);
if(f[a[i]-1]&&a[i]>1)
add(i,a[i]+n-1,x);
if(f[a[i]+1]&&a[i]<n)
add(i,a[i]+n+1,x);
}
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
printf("Case #%d: ",k++);
dij();
// for(i=head[1];i!=-1;i=s[i].next)
// {
// printf("%d %d\n",s[i].to,s[i].w);
// }
}
return 0;
}