题目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++){ //不可到达，即为-1 if(i==j){ ans[i][j]=0; } else{ ans[i][j]=-1; } } } int A,B,C; //A代表路口1，B代表路口2，路口1到路口2耗时为C for(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; //那就不动，然后continue if(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("%d ",ans[1][N]); //输出由路口1到路口N的时间 } return 0; } /************************************************************** Problem: 1447 User: lcyvino Language: C++ Result: Accepted Time:20 ms Memory: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 temp; temp.cost=c; temp.next=b; edge[a].push_back(temp); temp.next=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("%d ",Dis[n]); } return 0; } /************************************************************** Problem: 1447 User: lcyvino Language: 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 temp; temp.cost=c; temp.next=b; edge[a].push_back(temp); temp.next=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("%d ",Dis[n]); } return 0; } /************************************************************** Problem: 1447 User: lcyvino Language: C++ Result: Accepted Time:10 ms Memory: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，花费为p int s,t; //起点s，终点t while(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=d; temp.co=p; temp.next=b; edge[a].push_back(temp); temp.next=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 %d ",dis[t],cost[t]); } return 0; } /************************************************************** Problem: 1008 User: lcyvino Language: 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=d; temp.cost=p; temp.next=b; edge[a].push_back(temp); temp.next=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 %d ",Dis[t],Cost[t]); } return 0; } /************************************************************** Problem: 1008 User: lcyvino Language: C++ Result: Accepted Time:10 ms Memory:1552 kb ****************************************************************/