1030. Travel Plan (30)

IDEA

1.求最短路径，并输出该路径

2.要就在判断过程中若存在相同长度，则选cost小的

3.Dijkstra改进

思想：把图中node分为两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。

步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。

CODE

#include<iostream>
#include<vector> 
#include<stack>
#include<fstream>
using namespace std;
#define Max 500
#define INF 0x6FFFFFFFstruct Edge{int end;int distance;int cost;Edge(int e,int d,int c):end(e),distance(d),cost(c){}
};
struct Node{int distance;int cost;int path;Node():distance(INF),cost(INF),path(-1){}
};
vector< vector<Edge> > map;
vector<Node> city;
int visited[Max]={0};
int n,m,start,dest;
int FindMin(){//选择一个距离最小的点int min=INF;int k=-1;for(int i=0;i<n;i++){if(!visited[i]&&city[i].distance<min){min=city[i].distance;k=i;}}return k;
}
void Dijkstra(int start,int dest){city.clear();city.resize(n);city[start].distance=0;city[start].cost=0;while(1){int p=FindMin();//cout<<p<<endl;if(p==-1){return;}visited[p]=1;for(int i=0;i<map[p].size();i++){int q=map[p][i].end;int cost=map[p][i].cost;int dis=map[p][i].distance;if(!visited[q]){if(city[q].distance>city[p].distance+dis){city[q].distance=city[p].distance+dis;city[q].cost=city[p].cost+cost;city[q].path=p;//q前面的一个点是p }else if(city[q].distance==city[p].distance+dis&&city[q].cost>city[p].cost+cost){city[q].cost = city[p].cost+cost;  city[q].path =p; }}}}
}
void output(int p){stack<int> res;res.push(p);while(city[p].path!=-1){p=city[p].path;res.push(p);}while(!res.empty()){cout<<res.top()<<" ";res.pop();}
}
int main(){#ifndef ONLINE_JUDGEfreopen("input.txt","r",stdin);#endifcin>>n>>m>>start>>dest;map.clear();map.resize(n);for(int i=0;i<m;i++){int c1,c2,dis,cost;cin>>c1>>c2>>dis>>cost;map[c1].push_back(Edge(c2,dis,cost));map[c2].push_back(Edge(c1,dis,cost));}Dijkstra(start,dest);output(dest);cout<<city[dest].distance<<" "<<city[dest].cost<<endl;#ifndef ONLINE_JUDGEfclose(stdin);#endifreturn 0;
}