1081 : 最短路径·一

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

万圣节的早上，小Hi和小Ho在经历了一个小时的争论后，终于决定了如何度过这样有意义的一天——他们决定去闯鬼屋！

在鬼屋门口排上了若干小时的队伍之后，刚刚进入鬼屋的小Hi和小Ho都颇饥饿，于是他们决定利用进门前领到的地图，找到一条通往终点的最短路径。

鬼屋中一共有N个地点，分别编号为1…N，这N个地点之间互相有一些道路连通，两个地点之间可能有多条道路连通，但是并不存在一条两端都是同一个地点的道路。那么小Hi和小Ho至少要走多少路程才能够走出鬼屋去吃东西呢？
提示：顺序！顺序才是关键。
输入

每个测试点（输入文件）有且仅有一组测试数据。

在一组测试数据中：

第1行为4个整数N、M、S、T，分别表示鬼屋中地点的个数和道路的条数，入口（也是一个地点）的编号，出口（同样也是一个地点）的编号。

接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。

对于100%的数据，满足N<=10^3，M<=104, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。

对于100%的数据，满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。
输出

对于每组测试数据，输出一个整数Ans，表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。

样例输入

5 23 5 4 1 2 708 2 3 112 3 4 721 4 5 339 5 4 960 1 5 849 2 5 98 1 4 99 2 4 25 2 1 200 3 1 146 3 2 106 1 4 860 4 1 795 5 4 479 5 4 280 3 4 341 1 4 622 4 2 362 2 3 415 4 1 904 2 1 716 2 5 575 

样例输出

123 

思路

没有思路，都是模板。。。。 由于太久没做最短路径了，找了一道模板题练练手，刚好我的博客里也没有最短路径，不妨用这题来开个荤，分别用了Dijkstra 和 SPFA 解决这个题目。这题就是一题典型的模板题，不用什么思路。。。。。。。

Dijkstra算法 + 优先队列优化

#include <iostream> #include <algorithm> #include <string> #include <queue> #include <cstring> #include <cmath> #include <vector> #include <set> #include <map> using namespace std; struct node{ int v; int w; node(int a,int b){v=a;w=b;} node(){} friend bool operator<(node a,node b){ return a.w>b.w; } }; const int maxn=1010; const int inf=1<<27; int n,m,s,t; int a,b,len; vector<node> g[maxn]; bool vis[maxn]={false}; priority_queue<node> q; int d[maxn]; void dijk(int s) { fill(d,d+maxn,inf);  d[s]=0;  q.push(node(s,0)); while(!q.empty()) { int u=q.top().v;   q.pop(); if(vis[u]) continue;   vis[u]=1; for(int i=0;i<g[u].size();i++) { int v=g[u][i].v; int w=g[u][i].w; if(vis[v]==false) { if(d[v] > d[u]+w)      d[v] = d[u] + w;     q.push(node(v,d[v])); } } } } int main() {    cin>>n>>m>>s>>t; while(m--) {      cin>>a>>b>>len;      g[a].push_back(node(b,len));      g[b].push_back(node(a,len)); } dijk(s);        cout<<d[t]; return 0; } 

SPFA

朴素SPFA：

加了SLF后（推荐这个）：

spfa的SLF优化就是small label first 优化，当加入一个新点v的时候如果此时的dis[v]比队首dis[q.front()]还要小的话，就把v点加入到队首，否则把他加入到队尾，因为先扩展最小的点可以尽量使程序尽早的结束

代码：

#include <iostream> #include <algorithm> #include <string> #include <queue> #include <cstring> #include <cmath> #include <vector> #include <set> #include <map> using namespace std; struct node{ int v; int w; node(int a,int b){v=a;w=b;} }; const int maxn=100050; const int inf=1<<27; int n,m,s,t; int a,b,len; vector<node> g[maxn]; bool inq[maxn]={false}; int d[maxn]; //int num[maxn]={0}; /*bool*/ void SPFA(int s) { fill(d,d+maxn,inf);  deque<int> q;  d[s]=0;  q.push_back(s);  inq[s]=1; //num[s]=1; while(!q.empty()) { int u=q.front();   q.pop_front(); //推出队首   inq[u]=0; for(int i=0;i<g[u].size();i++) { int v=g[u][i].v; int w=g[u][i].w; if(d[v] > d[u]+w ) {     d[v] = d[u] + w; if(!inq[v]) { if(d[v] < d[q.front()])      q.push_front(v); //小于队首，放队首 else      q.push_back(v); //大于等于队首，放队尾         inq[v]=1; /*if(++num[v]>n)         return true;*/ } } } } //return false; } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); while(m--) { scanf("%d%d%d",&a,&b,&len);      g[a].push_back(node(b,len));      g[b].push_back(node(a,len)); } SPFA(s); /*if(SPFA(s) || d[t]==inf) // 有负环或无法走到          printf("circlen");      else*/ printf("%d", d[t]); return 0; } 

加了SLF+LLL后：

反而变慢了。。。。。LLL有点迷。。。以后少用。。。。 也许是我的代码问题。。。

设队首元素为 k ，每次松弛时进行判断，队列中所有 d 值的平均值为 x 。
若 d[ k ] > x ，则将 k 插入到队尾，查找下一元素，直到找到某一个 k 使得 d[ k ] <= x ，则将 k 出队进行松弛操作。

附代码：

代码:

#include <iostream> #include <algorithm> #include <string> #include <queue> #include <cstring> #include <cmath> #include <vector> #include <set> #include <map> using namespace std; struct node{ int v; int w; node(int a,int b){v=a;w=b;} }; const int maxn=100050; const int inf=1<<27; int n,m,s,t; int a,b,len; vector<node> g[maxn]; bool inq[maxn]={false}; int d[maxn]; int sum=0,cnt=0; //int num[maxn]={0}; /*bool*/ void SPFA(int s) { fill(d,d+maxn,inf);  deque<int> q;  d[s]=0;  q.push_back(s);  inq[s]=1; //num[s]=1; while(!q.empty()) { int u=q.front();   q.pop_front(); if(d[u]*cnt>sum) {    q.push_back(u); continue; }   sum-=d[u];   cnt--;   inq[u]=0; for(int i=0;i<g[u].size();i++) { int v=g[u][i].v; int w=g[u][i].w; if(d[v] > d[u]+w ) {     d[v] = d[u] + w; if(!inq[v]) { if(d[v] < d[q.front()])      q.push_front(v); else      q.push_back(v);               inq[v]=1;          cnt++;         sum+=d[v]; /*if(++num[v]>n)         return true;*/ } } } } //return false; } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); while(m--) { scanf("%d%d%d",&a,&b,&len);      g[a].push_back(node(b,len));      g[b].push_back(node(a,len)); } SPFA(s); /*if(SPFA(s) || d[t]==inf) // 有负环或无法走到          printf("circlen");      else*/ printf("%d", d[t]); return 0; }