首页 > 代码库 > poj3255
poj3255
1 #include<iostream> 2 #include<queue> 3 #define INF 1000000 4 using namespace std; 5 typedef pair<int,int> P; //first是最短距离,second是顶点编号 6 struct edge 7 { 8 int to,cost; 9 edge(int tt,int cc) 10 { 11 to=tt; 12 cost=cc; 13 } 14 }; 15 const int maxn=5010; 16 const int maxr=100010; 17 int n,r; 18 //图的邻接表表示 19 vector<edge> G[maxr]; 20 int dist[maxn]; 21 int dist2[maxn]; 22 void solve() 23 { 24 //把每个顶点当前的最短距离用堆维护 25 //每次从堆中取出的最小值就是下一次要使用的顶点 26 //在每次更新时往堆里插入当前最短距离和顶点的值对 27 //当取出的最小值不是最短距离的话,就丢弃这个值 28 priority_queue<P,vector<P>,greater<P> > que; 29 fill(dist,dist+n,INF); 30 fill(dist2,dist2+n,INF); 31 dist[0]=0; 32 que.push(P(0,0)); 33 while(!que.empty()) 34 { 35 P p=que.top(); 36 que.pop(); 37 int v=p.second,d=p.first; 38 if(d>dist2[v]) continue; 39 for(int i=0; i<G[v].size(); i++) 40 { 41 edge e=G[v][i]; 42 int d2=d+e.cost; 43 if(d2<dist[e.to]) 44 { 45 swap(d2,dist[e.to]); 46 que.push(P(dist[e.to],e.to)); 47 } 48 if(d2<dist2[e.to]&&dist[e.to]<d2) //次短路 49 { 50 dist2[e.to]=d2; 51 que.push(P(dist2[e.to],e.to)); 52 } 53 } 54 } 55 56 /* 57 for(int i=0; i<n; i++) 58 { 59 cout<<dist[i]<<" "<<dist2[i]<<endl; 60 }*/ 61 cout<<dist2[n-1]<<endl; 62 } 63 int main() 64 { 65 cin>>n>>r; 66 int from,to,cost; 67 for(int i=0; i<r; i++) 68 { 69 cin>>from>>to>>cost; 70 from--; 71 to--; 72 G[from].push_back(edge(to,cost)); 73 G[to].push_back(edge(from,cost)); 74 } 75 solve(); 76 return 0; 77 }
poj3255
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。