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.

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

这个是一个增加了一点条件的最短路，就是每一个点属于一层，然后某一层上的点可以花费C到达它上一层的任意一个点，或者到它下一层的任意一个点上，这样就相当于相邻层的点两两之间有一条权值为C的边，但是这样建边的话，边数太多，复杂度太高，所以就要想着优化一点，可以把某一层当成一个点，相邻层的点连一条权值为C单向边到这个点上，这个点连一条权值为0的单向边到当前层的所有点上，相邻层与层之间也要连一条边（如果某一层上没有点就不用连了），这样的话就可以减少很多条边，然后跑一遍dijkstra就可以了。

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int maxn = 220000;
const int inf = 1e8;
struct edge
{
    int to,cost;
    edge(int a,int b)
    {
        to = a;
        cost = b;
    }
    friend bool operator <(edge a,edge b)
    {
        return a.cost > b.cost;
    }
};

int n,m,c;
int dis[maxn];
vector<edge> e[maxn];
void dj(int s)
{
    int i,j;
    priority_queue<edge> q;
    for(i=1;i<=2*n;i++)
        dis[i] = inf;
    dis[s] = 0;
    q.push(edge(s,0));
    while(!q.empty())
    {
        edge t = q.top();
        q.pop();
        for(i=0;i<e[t.to].size();i++)
        {
            edge es = e[t.to][i];
            if(dis[es.to] > dis[t.to] + es.cost)
            {
                dis[es.to] = dis[t.to] + es.cost;
                q.push(edge(es.to,dis[es.to]));
            }
        }
    }
}
int ex[110000],lay[110000];
int main(void)
{
    int T,i,j;
    scanf("%d",&T);
    int cas = 1;
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&c);
        memset(ex,0,sizeof(ex));
        for(i=1;i<=2*n;i++)
            e[i].clear();
        for(i=1;i<=n;i++)
        {
            scanf("%d",&lay[i]);
            ex[lay[i]] = 1;
        }
        for(i=1;i<n;i++)
        {
            if(ex[i]==1 && ex[i+1]==1)
            {
                int x = n+i;
                int y = n+i+1;
                e[x].push_back(edge(y,c));
                e[y].push_back(edge(x,c));
            }
        }
        for(i=1;i<=n;i++)
        {
            e[lay[i]+n].push_back(edge(i,0));
            if(lay[i] > 1)
                e[i].push_back(edge(lay[i]-1+n,c));
            if(lay[i] < n)
                e[i].push_back(edge(lay[i]+1+n,c));
        }
        for(i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            e[x].push_back(edge(y,z));
            e[y].push_back(edge(x,z));
        }
        dj(1);
        printf("Case #%d: ",cas++);
        if(dis[n] == inf)
            printf("-1\n");
        else
            printf("%d\n",dis[n]);
    }

    return 0;
}

秒客网

hdu 4725 The Shortest Path in Nya Graph（最短路）

相关文章