This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0423" #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../graph/dijkstra.cpp" #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; vector<int> ts(n),es(n); for(int i=0;i<n;i++) cin>>ts[i]>>es[i]; Dijkstra<int> G(n+1); for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; a--;b--;c--; G.add_edge(b,a,c); } for(int i=0;i<n;i++) G.add_edge(n,i,ts[i]); G.build(n); long long ans=0; for(int i=0;i<n;i++) ans+=(long long)G[i]*es[i]; cout<<ans<<endl; return 0; }
#line 1 "test/aoj/0423.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0423" #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "graph/dijkstra.cpp" #line 3 "graph/dijkstra.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> struct Dijkstra{ struct Edge{ int to; T cost; Edge(int to,T cost):to(to),cost(cost){} bool operator<(const Edge &o)const{return cost>o.cost;} }; vector< vector<Edge> > G; vector<T> ds; vector<int> bs; Dijkstra(int n):G(n){} void add_edge(int u,int v,T c){ G[u].emplace_back(v,c); } void build(int s){ int n=G.size(); ds.assign(n,numeric_limits<T>::max()); bs.assign(n,-1); priority_queue<Edge> pq; ds[s]=0; pq.emplace(s,ds[s]); while(!pq.empty()){ auto p=pq.top();pq.pop(); int v=p.to; if(ds[v]<p.cost) continue; for(auto e:G[v]){ if(ds[e.to]>ds[v]+e.cost){ ds[e.to]=ds[v]+e.cost; bs[e.to]=v; pq.emplace(e.to,ds[e.to]); } } } } T operator[](int k){return ds[k];} vector<int> restore(int to){ vector<int> res; if(bs[to]<0) return res; while(~to) res.emplace_back(to),to=bs[to]; reverse(res.begin(),res.end()); return res; } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/aoj/0423.test.cpp" #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; vector<int> ts(n),es(n); for(int i=0;i<n;i++) cin>>ts[i]>>es[i]; Dijkstra<int> G(n+1); for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; a--;b--;c--; G.add_edge(b,a,c); } for(int i=0;i<n;i++) G.add_edge(n,i,ts[i]); G.build(n); long long ans=0; for(int i=0;i<n;i++) ans+=(long long)G[i]*es[i]; cout<<ans<<endl; return 0; }