首页 > ACM题库 > HDU-杭电 > HDU 4725-The Shortest Path in Nya Graph-最短路径-[解题报告]HOJ
2015
09-17

HDU 4725-The Shortest Path in Nya Graph-最短路径-[解题报告]HOJ

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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

Case #1: 2
Case #2: 3

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4725

题意:有N个点和N层..一层有X个点(0<=X<=N).两邻两层间有一条路花费C。还有M条小路在两个点之间。问从第一个点走到第N个点最短路是多少…

题解:依然是在点之间SPFA。不过在跑的时候不仅要跑与当前点相连接的点。还有把当前点所在层的相邻层的点判断是否加入队列…

CODE:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

#define mkp make_pair
#define fst first
#define scd second

using namespace std;
int dis[100011];
int vis[100011];
int lay[100011];
vector<int>vec[100011];
struct Edge_t{
    int to,next,cap;
}edge[500000];
int head[100011],et;

inline void adde(int u,int v,int w){
    edge[et].to=v;
    edge[et].cap=w;
    edge[et].next=head[u];
    head[u]=et++;
}

inline void spfa(int n,int C){
    queue<int>q;
    q.push(1);
    memset(vis,0,sizeof vis);
    memset(dis,-1,sizeof dis);
    dis[1]=0;
    int e,u,v,size,i,k;
    while(!q.empty()){
        u=q.front();q.pop();
        vis[u]=0;
        for(e=head[u];~e;e=edge[e].next){
            v=edge[e].to;
            if(dis[v]<0 || dis[v]>dis[u]+edge[e].cap){
                dis[v]=dis[u]+edge[e].cap;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
        if(lay[u]>1){
            size=vec[k=(lay[u]-1)].size();
            for(i=0;i<size;++i){
                v=vec[k][i];
                if(dis[v]<0 || dis[v]>dis[u]+C){
                    dis[v]=dis[u]+C;
                    if(!vis[v]){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        if(lay[u]<n){
            size=vec[k=lay[u]+1].size();
            for(i=0;i<size;++i){
                v=vec[k][i];
                if(dis[v]<0 || dis[v]>dis[u]+C){
                    dis[v]=dis[u]+C;
                    if(!vis[v]){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
            
        }
    }
}

int main(){
    int t,tt=0,C;
    int n,m,u,v,i,size,w;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&C);
        memset(head,-1,sizeof head);et=0;
        memset(vis,0,sizeof vis);
        for(i=1;i<=n;++i){
            scanf("%d",&lay[i]);//第i个点所以层为lay[i]
            vec[i].clear();
        }
        while(m--){
            scanf("%d%d%d",&u,&v,&w);
            adde(u,v,w);adde(v,u,w);
            if(!vis[u]){//把点加入层..
                vec[lay[u]].push_back(u);
                vis[u]=1;
            }
            if(!vis[v]){
                vec[lay[v]].push_back(v);
                vis[v]=1;
            }
        }
        if(!vis[1])//始点和终于一定要在某一层内..
            vec[lay[1]].push_back(1);
        if(!vis[n])
            vec[lay[n]].push_back(n);
        for(i=1;i<=n;++i)//如果某一层没有点
			if(vec[lay[i]].empty())
                vec[lay[i]].push_back(i);
        spfa(n,C);
        printf("Case #%d: %d\n",++tt,dis[n]);
    }
    return 0;
}

参考:http://blog.csdn.net/madrishing/article/details/11626163