1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> using namespace std;
#define LL long long
const int CN = 1e5+5; const LL INF = 0x3f3f3f3f3f3f3f2f;
LL read(){ LL s = 0,ne = 1; char c = getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1; for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0'; return s*ne; }
class fs{ public: int to,nxt; LL di; void init(int t,int n,LL d) {to=t;nxt=n;di=d;} }E[CN * 51]; int hd[CN],ecnt = 0; void add(int x,int y,LL z) {E[++ecnt].init(y, hd[x], z); hd[x] = ecnt;}
int n,m;
class DJ{ public: int id; LL v; bool operator < (const DJ& a)const {return v > a.v;} }; priority_queue<DJ> Q; LL d[CN]; bool vis[CN]; LL SP(int st,int ed){ memset(vis, 0, sizeof(vis)); memset(d, 0x3f, sizeof(d)); Q.push((DJ){st, d[st] = 0}); while(!Q.empty()){ int u = Q.top().id; Q.pop(); if(vis[u]) continue; vis[u] = true; for(int k = hd[u]; k; k = E[k].nxt){ int v = E[k].to; if(d[v] > d[u] + E[k].di){ d[v] = d[u] + E[k].di; Q.push((DJ){v, d[v]}); } } } return d[ed] < INF ? d[ed] : -1; }
int main() { n = read(); m = read(); while(m--){ int u = read(),v = read(); LL c = read(); add(u, v, c); } for(int i=1;i<n;i++) add(i + 1, i, 0);
printf("%lld", SP(1, n)); return 0; }
|