codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<ctime> #include<vector> #include<queue> #include<set> #include<map> #include<algorithm> #include<utility> using namespace std; typedef pair<int,int> P; const int INF=201303160; int n,r; vector<P> g[10000]; int d1[10000],d2[10000]; priority_queue<P,vector<P>,greater<P> > q; void cln() { memset(g,0,sizeof(g)); for(int i=1;i<=n;i++) d1[i]=d2[i]=INF; } void init() { for(int i=1;i<=r;i++) { int s,t,v; scanf("%d%d%d",&s,&t,&v); g[s].push_back(P(v,t)); g[t].push_back(P(v,s)); } } void dijkstra() { d1[1]=0;q.push(P(0,1)); while(!q.empty()) { P pnt=q.top();q.pop(); int v=pnt.first; int frm=pnt.second; if(v>d2[frm]) continue;//*** for(int i=0;i<g[frm].size();i++) { int to=g[frm][i].second; int vv=g[frm][i].first+v; if(vv<d1[to]) { swap(d1[to],vv); //***!当之前的最小值被新值顶替时,它一样也可以参加次小值的竞争! q.push(P(d1[to],to)); } if(vv<d2[to] && vv>d1[to]) { d2[to]=vv; q.push(P(d2[to],to)); } } } } int main() { while(scanf("%d%d",&n,&r)!=EOF) { cln(); init(); dijkstra(); printf("%d\n",d2[n]); } return 0; }
Private
[
?
]
Run code
Submit