HDU 4725 The Shortest Path in Nya Graph [构造 + 最短路]

HDU - 4725 The Shortest Path in Nya Graph

http://acm.hdu.edu.cn/showproblem.php?pid=4725
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 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.

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

这题的题意是有1-n个点，分布在1-n的若干层上，一层上有可能很多的点，也可能没有点。两个相邻的层上的点可以花费C连通，除此之外还有m条边。求从点1到点n的最短路径。
这题其实就是构造，因为相邻的层之间的点可以建权重是C的边，如果点i在r层，那么假设层r所在的点是r+n，实际上就是建立从点i到点r+n的权重为0的有向边，当有点j位于第r+1层或者r-1层时，实际上就是建立从点r+n到点j的权重为C的有向边。最后去做一个ElogE的Dijkstra就行了。
这题要注意的就是把层抽象化成点之后，点的个数实际上是多了一倍，开数组的时候一定要记得乘2。（没有*2哇了两个小时（泣））

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <string>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#include <map>

#define INF 0x3f3f3f3f

#define lowbit(x) (x&(-x))

using namespace std;

typedef long long ll;

const int maxn = 1e5+;

const int N = 1e4+;

const int mol = 1e9+;

int arr[maxn],l[maxn],r[maxn],vis[N];

vector <int> vi[N];

int main()

{

    for(int i=;i<N;i++)

        for(int j=;j<=sqrt(i);j++)

            if(i%j == )

            {

                vi[i].push_back(j);

                if(j*j != i) vi[i].push_back(i/j);

            }

    int n;

    while(~scanf("%d",&n))

    {

        memset(l,,sizeof(l));

        memset(r,,sizeof(r));

        memset(vis,,sizeof(vis));

        ll ans = ;

        for(int i=;i<=n;i++)

            scanf("%d",&arr[i]);

        for(int i=;i<=n;i++)

        {

            int tp = ;

            for(int j=;j<vi[arr[i]].size();j++)

                tp = max(tp,vis[vi[arr[i]][j]]);

            l[i] = tp;

            //cout << tp << " ";

            vis[arr[i]] = i;

        }

        //cout << endl;

        for(int i=;i<N;i++) vis[i] = n+;

        for(int i=n;i>;i--)

        {

            int tp = n+;

            for(int j=;j<vi[arr[i]].size();j++)

                tp = min(tp,vis[vi[arr[i]][j]]);

            //cout << tp << " ";

            r[i] = tp;

            vis[arr[i]] = i;

        }

        //cout << endl;

        for(int i=;i<=n;i++)

            ans = (ans + 1LL*(i-l[i])*(r[i]-i) % mol) % mol;

        printf("%lld\n",ans);

    }

}

巴特西

HDU 4725 The Shortest Path in Nya Graph [构造 + 最短路]

HDU - 4725 The Shortest Path in Nya Graph

最新文章

热门文章