1030. Travel Plan
考察最短路及其路径记录
[cpp]
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define INF 0x6FFFFFFF
typedef struct Node
{
int dis, cost, path;
Node(){dis=INF; cost=INF; path=-1;}
}Node;
typedef struct Edge
{
int end, dis, cost;
Edge(int e, int d, int c){end = e; dis = d; cost = c;}
};
int n, m, s, t;
vector<vector<Edge>> edge;
vector<int> path;
vector<Node> city;
std::vector<bool> visited;
int FindMin()
{
int mmin = INF;
int k = -1;
for (int i = 0; i < n; ++i)
{
if(!visited[i] && city[i].dis < mmin)
{
mmin = city[i].dis;
k = i;
}
}
return k;
}
void Dijkstra(int s, int t)
{
visited.assign(n, false);
city.clear();
city.resize(n);
city[s].dis = 0; city[s].cost = 0;
while(true)
{
int u = FindMin();
if(u == -1)
return;
visited[u] = true;
for (int i = 0; i < edge[u].size(); ++i)
{
int v = edge[u][i].end;
int cost = edge[u][i].cost;
int dis = edge[u][i].dis;
if (!visited[v])
{
if (city[v].dis > city[u].dis+dis)
{
city[v].dis = city[u].dis+dis;
city[v].cost = city[u].cost+cost;
city[v].path = u;
}
else if (city[v].dis == city[u].dis+dis
&& city[v].cost > city[u].cost+cost)
{
city[v].cost = city[u].cost+cost;
city[v].path = u;
}
}
}
}
}
void OutputPath(int t)
{
stack<int> ans;
ans.push(t);
while(city[t].path != -1)
{
t = city[t].path;
ans.push(t);
}
while (!ans.empty())
{
printf("%d ", ans.top());
ans.pop();
}
}
int main()
{
while (scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
{
edge.clear();
edge.resize(n);
while (m--)
{
int u, v, d, c;
scanf("%d%d%d%d",&u,&v,&d,&c);
edge[u].push_back(Edge(v, d, c));
edge[v].push_back(Edge(u, d, c));
}
//dijkstra
Dijkstra(s, t);
OutputPath(t);
printf("%d %d\n",city[t].dis, city[t].cost);
}
return 0;
}
补充：软件开发 , C++ ,
