时间限制：400ms
A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (<=500) is the number of cities (and hence the cities are numbered from 0 to N-1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:
City1 City2 Distance Cost
where the numbers are all integers no more than 500, and are separated by a space.
Output Specification:
For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.
Sample Input
4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20
Sample Output
0 2 3 3 40
=================================================
这题目嘛是单元最短路径算法的变种，主要变了俩地方：
1.最短路径可能不止1条
2.最后找出最短路中权重cost最小的一个
我不知道我的解法中数据结构是否有冗余的，不过反正是通过了（可能内存多占点吧）
主要就是用Dijkstra算法，但是
1.更新距离组
2.多算一个
，更新条件是：A)发现了更好的距离的时候，直接更新权重组，因为距离是首先要考虑的
B)发现了和现在相同的距离的时候，如果cost比较小，更新一下
这样等Dijkstra算法结束后，我们已经能得到最短距离且权重cost最小的路径了。以前还想着再根据最短距离的各种回溯遍历一下求最小耗费，今天一想其实根本不需要！
算法中还有点不确定的地方，见下面的注释。
====================================================
#include
#include
#include
#include
using namespace std;
struct Node
{
vector
int best_dist;
int best_cost;
int best_cost_from;
vector
Node()
{
best_dist = 65535;
best_cost = 65535;
best_cost_from = -1;
}
};
int main()
{
int N, M, S, D;
scanf("%d %d %d %d", &N, &M, &S, &D);
int **distances = new int*[N];
int **costs = new int*[N];
Node *nodes = new Node[N];
set
for(int i=0; i
for(; it!=ptrCurrNode->linkedNodes.end(); it++)
{
int linkedId = *it;
if( working.find(linkedId) == working.end())
{
//这个点已经是确定点了...
//是不是不再考虑?
}
Node *ptrLinkedNode = &nodes[linkedId];
int distViaMe = ptrCurrNode->best_dist + distances[last_found_best][linkedId];
int costViaMe = ptrCurrNode->best_cost + costs[last_found_best][linkedId];
if(distViaMe < ptrLinkedNode->best_dist)
{
ptrLinkedNode->best_dist = distViaMe;
ptrLinkedNode->best_from.clear();
ptrLinkedNode->best_from.push_back(last_found_best);
ptrLinkedNode->best_cost = costViaMe;
ptrLinkedNode->best_cost_from = last_found_best;
}
else if (distViaMe == ptrLinkedNode->best_dist)
{
ptrLinkedNode->best_from.push_back(last_found_best);
if(costViaMe < ptrLinkedNode->best_cost)
{
ptrLinkedNode->best_cost = costViaMe;
ptrLinkedNode->best_cost_from = last_found_best;
}
}
}
//更新完后找出不确定点中最小距离的，加入确定点中
int minDist = 65535;
set
for(; set_it != working.end(); set_it++)
{
int id = *set_it;
if( nodes[id].best_dist < minDist)
{
minDist = nodes[id].best_dist;
last_found_best = id;
}
}
set_it = working.find(last_found_best);
working.erase(set_it);
}
//第三步
stack
int currIndex = D;
while(currIndex != S)
{
route.push(currIndex);
currIndex = nodes[currIndex].best_cost_from;
}
printf("%d ", S);
while(!route.empty())
{
printf("%d ", route.top());
route.pop();
}
printf("%d %d", nodes[D].best_dist, nodes[D].best_cost);
return 0;
}
======================================================
测试点 结果 用时(ms) 内存(kB) 得分/满分 0 答案正确 0 710 18/18 1 答案正确 0 790 6/6 2 答案正确 0 2570 6/6