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:

。建好图之后跑一遍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;
}