HDU - 4725 The Shortest Path in Nya Graph(最短路)好题好题

上题：

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 <= 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.

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

Sample Output

Case #1: 2
Case #2: 3

题目的大意就是：他现在给你n个点 ，这些点的分布是层型分布的，你可以从第i层走到相邻的层（i+1，i-1）中，这样走的花费是c，接着他会给你m（从u->v）条小路，从小路走的花费 是w，问你从1->n所走的最小花费是多少。

思路：

这就是一个建图的问题，建图真是一门博大精深的学问啊 。。。我的做法是 你把每一层在抽象成一个点，比如说样例1 他的一号顶点在第一层，那我们就在抽象出一个i+n也就是第4号点，那么三号顶点就是在第5号点，so on，这样4->5相邻层之间的权值就是c，之后相同层之间的权值为0，比如4->1权值为0，但是这里是有坑点的就是，你只用建4->1的边 而不用建1->4的边。。和只有相邻的层中有点你才可以建边，这个问题在代码中很详细的说了。下面说一下我worng了 n多发的原因，一个就是 多建了一条没有用的边，然后超时了，，，接着就是结构数组，开的是有问题的，我这样抽层建边的话，最多的条数应该是大于maxn的，这里也worng了好多发 ，接着就是层和点之间也是要建边的，这里大家应该是想到的，但是我竟然没想到。。。

现在上代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,c,cnt,i,k;
const int maxn=200005;
struct node
{
int next,to;
int value;
}edg[8*maxn];//最多建7条边，所以开8就够了，，原来开的是2，写完发现这个2写的真是太特么随便。。。xjb写个数就往上交。。欠思考，不严谨 
int p[maxn],head[maxn],dis[maxn];
bool vis[maxn],xx[maxn];
void add(int u,int v,int w)
{
edg[cnt].value=w;
edg[cnt].to=v;
edg[cnt].next=head[u];
head[u]=cnt++;
}
queue<int>que;
void spfa()
{
for(i=0;i<=2*n;i++)
{
dis[i]=INF;
vis[i]=0;
}
dis[1]=0;
vis[1]=1;
while(!que.empty())
{
que.pop();
}
que.push(1);
while(!que.empty())
{
k=que.front();
que.pop();
vis[k]=0;
for(int i=head[k];i!=-1;i=edg[i].next)
{
int v=edg[i].to;
if(dis[v]>dis[k]+edg[i].value)
{
dis[v]=dis[k]+edg[i].value;
if(!vis[v])
{
vis[v]=1;
que.push(v);
}

}
}
}
}
int main()
{
int oo;
scanf("%d",&oo);
int ca=0;
while(oo--)
{
memset(head,-1,sizeof(head));
memset(p,0,sizeof(p));
memset(xx,0,sizeof(xx));
memset(edg,0,sizeof(edg));
scanf("%d%d%d",&n,&m,&c);
cnt=0;
int t=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
xx[p[i]]=1;
}
for(int i=2;i<=n;i++)//相邻层建边 
{
if(xx[i]&&xx[i-1])//要有才建边 
{
add(i+n,i+n-1,c);
add(i+n-1,i+n,c);
}
}
for(int i=1;i<=n;i++)//同层之间建边 层与层之间也是要建边的 
{
//add(i,p[i]+n,0);多建一条从点到层的边对最短路是毫无影响的，况且这样的边会使相邻的两层如果没有点的话也会建边比如样例 
/*1
3 0 1
1 1 1*/ 
add(p[i]+n,i,0);
if(p[i]>1) add(i,n+p[i]-1,c);
            if(p[i]<n) add(i,n+p[i]+1,c);
}
int a,b,c;
for(int i=1;i<=m;i++)//点与点之间建边 
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
spfa();
printf("Case #%d: ",++ca);
        int ans=dis[n];
        if(ans<INF)
{
printf("%d\n",ans);
} 
        else
{
printf("-1\n");
} 
}
}

秒客网

HDU - 4725 The Shortest Path in Nya Graph(最短路)好题好题

相关文章