Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* e158 */
- /* AC (61ms, 3MB) */
- #include <cstdio>
- #include <queue>
- #include <vector>
- using namespace std;
- const int maxn = 50005 , INF = 1e9;
- struct Edge{
- int to , w;
- };
- vector <Edge> g[maxn];
- int cur = 0 , n , a , b , c , max0 = 0;
- int d[maxn];
- bool in[maxn];
- int spfa(int s , int t) {
- queue <int> q;
- fill(in, in + max0 + 1, 0);
- fill(d, d + max0 + 1, INF);
- d[s] = 0; q.push(s);
- while(q.size()) {
- int now = q.front(); q.pop(); in[now] = 0;
- for(int i = 0, l = g[now].size(); i < l; ++i) {
- int nex = g[now][i].to;
- if(d[nex] == INF || d[nex] < d[now] + g[now][i].w) {
- d[nex] = d[now] + g[now][i].w;
- if(!in[nex]) in[nex] = 1 , q.push(nex);
- }
- }
- }
- return d[t];
- }
- int main() {
- scanf("%d", &n);
- for(int i = 1; i <= n; ++i) {
- scanf("%d %d %d", &a, &b, &c);
- g[a - 1].push_back({b, c});
- max0 = max(max0, b);
- }
- for(int i = 0; i < max0; ++i) g[i].push_back({i + 1, 0}), g[i + 1].push_back({i, -1});
- printf("%d\n",spfa(0, max0));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement