Link: Shortest Path on a Line

Shortest Path on a Line

Problem solving:
We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices. In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph. The i-th operation is as follows:

The operation uses integers Li and Ri between 1 and N (inclusive), and a positive integer Ci. For every pair of integers (s,t) such that Li≤s<t≤Ri, add an edge of length Ci between Vertex s and Vertex t.
The integers L1,…,LM, R1,…,RM, C1,…,CM are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints
2≤N≤1e5
1≤M≤1e5
1≤Li<Ri≤N
1≤Ci≤1e9
Input
Input is given from Standard Input in the following format:

N M
L1 R1 C1
:
LM RM CM

Output
Print the length of the shortest path from Vertex 1 to Vertex N in the final graph. If there is no shortest path, print -1 instead.

Sample Input 1
4 3
1 3 2
2 4 3
1 4 6
Sample Output 1
5
We have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of length 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between Vertex 1 and Vertex 4.

Sample Input 2
4 2
1 2 1
3 4 2
Sample Output 2
-1
Sample Input 3
10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3
Sample Output 3
28

Problem solving:
这道题的意思是，给你n个节点，然后给你m组L，R，C。代表着从L到[L+1,R]内的任何一个节点都有一条权值为C的边，让你求从1到n的最短距离。

如果每次输入LR之后都暴力建边的话，时间复杂度是O(N^2)的。所以这道题很巧妙的点就来了，你可以先预处理一下。

对除了1节点的每一个节点都与它的上一个节点之间建一条权值为0的有向边，即i--->i-1(i!=1)，这样以后输入LRC之后就建一条从L到R的一条权值为C的边，这样就相当于从L到[L+1,R]内的任何一个节点都有一条权值为C的边。因为中间点之间的权值都为0.这样优化一下时间复杂度就是O(nlogn)了
。建好图之后跑一遍Dijkstra就行了。

Code:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
ll       n, m, vis[maxn], dis[maxn];
#define pil    pair<ll, ll>
#define vec    vector<pil>
#define pb     push_back
#define mp     make_pair
vector<pil>                             V[maxn];
priority_queue<pil, vec, greater<pil> > q;
void init()
{
    for (int i = 2; i <= n; i++)
        V[i].pb(mp(i - 1, 0));
}
void solve()
{
    dis[1] = 0;
    for (int i = 2; i <= n; i++)
        dis[i] = INF;
    q.push(mp(dis[1], 1));
    while (!q.empty())
    {
        pil p = q.top(); q.pop();
        ll  x = p.second; if (vis[x])
            continue;
        vis[x] = 1;
        for (int i = 0; i < V[x].size(); i++)
        {
            ll y = V[x][i].first, d = V[x][i].second;
            if (vis[y])
                continue;
            if (dis[y] > dis[x] + d)
                dis[y] = dis[x] + d;
            q.push(mp(dis[y], y));
        }
    }
    if (dis[n] != INF)
        cout << dis[n] << endl;
    else
        cout << "-1\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    init();
    for (int i = 0, u, v, w; i < m; i++)
    {
        cin >> u >> v >> w;
        V[u].pb(mp(v, w));
    }
    solve();
    return 0;
}
赏