关于【最短路径】

关于【最短路径】

题目1447：最短路

题目描述：

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

输入：

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。
当输入为两个0时，输入结束。

输出：

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。

样例输入：

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

样例输出：

3
2

代码如下：（Floyd算法） 时间复杂度为O(n^3)，所以当结点数过多时并不好用

#include <iostream>
#include <stdio.h>using namespace std;int main()
{int ans[101][101];int N,M;while(scanf("%d%d",&N,&M)!=EOF&&N!=0&&M!=0){  //N代表路口数，M代表路径数for(int i=1;i<=N;i++){                    //进行初始化，刚开始时除了自己到自己设为0，其余设为for(int j=1;j<=N;j++){                //不可到达，即为-1if(i==j){ans[i][j]=0;}else{ans[i][j]=-1;}}}int A,B,C;                                //A代表路口1，B代表路口2，路口1到路口2耗时为Cfor(int i=1;i<=M;i++){scanf("%d%d%d",&A,&B,&C);ans[A][B]=ans[B][A]=C;                //因为是无向图，所以需要2次赋值
        }for(int k=1;k<=N;k++){                         //Floyd算法for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){if(ans[i][k]==-1||ans[k][j]==-1)   //如果路口i到路口k或者路口k到路口j就没有道路，continue;                      //那就不动，然后continueif(ans[i][j]==-1||ans[i][j]>(ans[i][k]+ans[k][j])){     //如果路口i到路口j原来是不通的，或者ans[i][j]=ans[i][k]+ans[k][j];                      //由路口i到路口j经过路口k的时间比从路口i}                                                       //直接到达路口j时间要短，就修改ans[i][j]的值
                }}}printf("%dn",ans[1][N]);           //输出由路口1到路口N的时间
    }return 0;
}/**************************************************************Problem: 1447User: lcyvinoLanguage: C++Result: AcceptedTime:20 msMemory:1520 kb
****************************************************************/

 采用Dijkstra算法，在Code::Blocks下运行无误，提交至OJ仍有问题，有待解决，代码如下：

#include <iostream>
#include <stdio.h>
#include <vector>using namespace std;struct Edge{int next;int cost;
};vector<Edge> edge[10010];
bool mark[110];
int Dis[110];int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF&&n!=0&&m!=0){int a,b,c;while(m--){scanf("%d%d%d",&a,&b,&c);Edge st==b;edge[a].push_back(temp);=a;edge[b].push_back(temp);}for(int i=1;i<=n;i++){mark[i]=false;Dis[i]=-1;}Dis[1]=0;mark[1]=true;int newP=1;for(int i=1;i<=n-1;i++){for(int j=0;j<=edge[newP].size()-1;j++){int t=edge[newP][j].next;int c=edge[newP][j].cost;if(mark[t]==true)continue;if(Dis[t]==-1||Dis[t]>Dis[newP]+c)Dis[t]=Dis[newP]+c;}int min=123123123;for(int i=1;i<=n;i++){if(mark[i]==true)continue;if(Dis[i]==-1)continue;if(Dis[i]<min){min=Dis[i];newP=i;}}mark[newP]=true;}printf("%dn",Dis[n]);}return 0;
}/**************************************************************Problem: 1447User: lcyvinoLanguage: C++Result: Wrong Answer
****************************************************************/

错误原因：没有对edge邻接链表初始化

 

for(int i=1;i<=n;i++){    //初始化edge[i].clear();
}

 

 

贴上正确的代码：

#include <iostream>
#include <stdio.h>
#include <vector>using namespace std;struct Edge{int next;int cost;
};vector<Edge> edge[105];
bool mark[105];
int Dis[105];int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;for(int i=1;i<=n;i++){   //初始化mark[i]=false;Dis[i]=-1;edge[i].clear();}int a,b,c;while(m--){scanf("%d%d%d",&a,&b,&c);Edge st==b;edge[a].push_back(temp);=a;edge[b].push_back(temp);}Dis[1]=0;mark[1]=true;int nowP=1;for(int i=1;i<n;i++){for(unsigned int j=0;j<=edge[nowP].size()-1;j++){int temp_next=edge[nowP][j].next;int temp_cost=edge[nowP][j].cost;if(mark[temp_next]==true)continue;if(Dis[temp_next]==-1||Dis[temp_next]>Dis[nowP]+temp_cost){Dis[temp_next]=Dis[nowP]+temp_cost;}}int min=999999999;for(int k=1;k<=n;k++){if(mark[k]==true)continue;if(Dis[k]==-1)continue;if(Dis[k]<min){min=Dis[k];nowP=k;}}mark[nowP]=true;}printf("%dn",Dis[n]);}return 0;
}/**************************************************************Problem: 1447User: lcyvinoLanguage: C++Result: AcceptedTime:10 msMemory:1520 kb
****************************************************************/

 

题目1008：最短路径问题

题目描述：

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入：

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)

输出：

输出 一行有两个数， 最短距离及其花费。

样例输入：

3 2
1 2 5 6
2 3 4 5
1 3
0 0

样例输出：

9 11

先贴上上次WA了n次的代码：

#include <iostream>
#include <stdio.h>
#include <vector>using namespace std;struct Edge{       //定义邻接链表里的结点int next;      //与结点直接相邻的另一个结点int len;       //长度int co;        //花费
};vector<Edge> edge[1010];  //邻接链表
bool mark[1010];    //标记结点是否已经求出最短路径
int dis[1010];      //两层意思；1、若已经求出最短路径，则存放的就是最短路径的值；//2、若最短路径还没有求出来，存放的是由起始结点到已求出//最短路径的结点集内一点加上到达该结点的最短的距离
int cost[1010];     //记录花费int main()
{int n,m;                        //n个点，m条无向边int a,b,d,p;                    //a和b之间有一条边，且其长度为d，花费为pint s,t;                        //起点s，终点twhile(scanf("%d%d",&n,&m)!=EOF&&n!=0&&m!=0){for(int i=1;i<=n;i++){edge[i].clear();        //清空
        }for(int i=1;i<=n;i++){      //初始化mark[i]=false;dis[i]=-1;cost[i]=0;}while(m--){scanf("%d%d%d%d",&a,&b,&d,&p);Edge temp;temp.len===b;edge[a].push_back(temp);=a;edge[b].push_back(temp);      //因为是无向图，故2次push_back(temp)
        }scanf("%d%d",&s,&t);mark[s]=true;dis[s]=0;int newP=s;for(int i=1;i<=n-1;i++){for(unsigned int j=0;j<=edge[newP].size()-1;j++){int temp_next=edge[newP][j].next;int temp_len=edge[newP][j].len;int temp_cost=edge[newP][j].co;if(mark[temp_next]==true)continue;if(dis[temp_next]==-1||dis[temp_next]>dis[newP]+temp_len||(dis[temp_next]==dis[newP]+temp_len&&cost[temp_cost]>cost[newP]+temp_cost)){//若距离相同，选择花费小的dis[temp_next]=dis[newP]+temp_len;       //更新cost[temp_next]=cost[newP]+temp_cost;    //更新
                }}int min=999999999;    //设定一个大数，比最大的dis大就行for(int i=1;i<=n;i++){if(mark[i]==true)continue;if(dis[i]==-1)continue;if(dis[i]<min){min=dis[i];newP=i;          //加入新结点的结点号
                }}mark[newP]=true;}printf("%d %dn",dis[t],cost[t]);}return 0;
}
/**************************************************************Problem: 1008User: lcyvinoLanguage: C++Result: Wrong Answer
****************************************************************/

再贴上今天AC的代码：

 

#include <iostream>
#include <stdio.h>
#include <vector>using namespace std;struct Edge{int next;int length;   //距离int cost;     //花费
};vector<Edge> edge[1005];
bool mark[1005];
int Dis[1005];
int Cost[1005];int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;for(int i=1;i<=n;i++){edge[i].clear();mark[i]=false;Dis[i]=-1;Cost[i]=0;}int a,b,d,p;while(m--){scanf("%d%d%d%d",&a,&b,&d,&p);Edge temp;temp.length=st==b;edge[a].push_back(temp);=a;edge[b].push_back(temp);}int s,t;scanf("%d%d",&s,&t);Dis[s]=0;mark[s]=true;int nowP=s;for(int i=1;i<n;i++){for(unsigned int j=0;j<=edge[nowP].size()-1;j++){int temp_next=edge[nowP][j].next;int temp_length=edge[nowP][j].length;int temp_cost=edge[nowP][j].cost;if(mark[temp_next]==true)continue;if((Dis[temp_next]==-1)||(Dis[temp_next]>Dis[nowP]+temp_length)||((Dis[temp_next]==Dis[nowP]+temp_length)&&(Cost[temp_next]>Cost[nowP]+temp_cost))){Dis[temp_next]=Dis[nowP]+temp_length;Cost[temp_next]=Cost[nowP]+temp_cost;}}int min=999999999;for(int i=1;i<=n;i++){if(mark[i]==true)continue;if(Dis[i]==-1)continue;if(Dis[i]<min){min=Dis[i];nowP=i;}}mark[nowP]=true;}printf("%d %dn",Dis[t],Cost[t]);}return 0;
}/**************************************************************Problem: 1008User: lcyvinoLanguage: C++Result: AcceptedTime:10 msMemory:1552 kb
****************************************************************/

 

 

 

转载于:.html