A1030
Description：
旅行者地图给出了两个城市沿着高速路的距离及每条高速路的费用。求起始城市至终止城市的最短路径，若最短路径不唯一，则输出具有最小花费的路径。
Input：
- 每个输入一组样例
- 首行给出四个正整数：城市数目N<=500，[0,N-1]，高速路条数M，起点S和终点D
- 接下来M行给出两个城市的距离及花销
- 所有数字不超过500
Output：
- 对于每个测试，将最短路上从起点到终点的所有城市依次打印出，最后给出总距离以及总花销。每个数字间用空格隔开。
不想说了，模板题Dijkstra + DFS，代码解析及模板请移步A1003 Emergency
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 505;
const int maxm = maxn*maxn/2;
const int inf = 0x3f3f3f3f;
typedef pair<int,int>PII;
set<PII, less<PII>>minheap;
struct edge{int cost;int distance;int v;int next;
}e[maxm];
int p[maxn], dis[maxn], eid;
int n, m, s, d;
bool vis[maxn];void init(){memset(p, -1, sizeof(p));memset(vis, 0, sizeof(vis));memset(dis, 0x3f, sizeof(dis));eid = 0;
}
void ins(int u, int v, int d, int c){e[eid].v = v;e[eid].distance = d;e[eid].cost = c;e[eid].next = p[u];p[u] = eid++;
}
void in(int u, int v, int d, int c){ins(u, v, d, c);ins(v, u, d, c);
}
bool dijkstra(){minheap.insert(PII(0, s));dis[s] = 0;for(int i = 0; i < n; i++){if(minheap.size() == 0)return false;auto it = minheap.begin();int v = it->second;minheap.erase(*it);vis[v] = true;for(int j = p[v]; j != -1; j = e[j].next){int x = e[j].v;if(!vis[x] && dis[v] + e[j].distance < dis[x]){minheap.erase(PII(dis[x], x));dis[x] = dis[v] + e[j].distance;minheap.insert(PII(dis[x], x));}}}return true;
}
vector<int>ans, record;
int cntCost = 0, cntDis = 0, minCost = inf;
void dfs(int now, int pre){if(now == d && cntDis == dis[d] && cntCost < minCost){minCost = cntCost;ans = record;return ;}if(cntDis >= dis[d] && cntCost >= minCost)return ;for(int i = p[now]; i != -1; i = e[i].next){int v = e[i].v;if(v != pre && cntDis + e[i].distance <= dis[d]&& cntCost + e[i].cost < minCost){cntDis += e[i].distance;cntCost += e[i].cost;record.push_back(v);dfs(v, now);record.pop_back();cntCost -= e[i].cost;cntDis -= e[i].distance;}}
}
int main()
{
#ifdef ONLINE_JUDGE
#elsefreopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGEscanf("%d%d%d%d", &n, &m, &s, &d);init();int u, v, td, tc;for(int i = 0; i < m; i++){scanf("%d%d%d%d", &u, &v, &td, &tc);in(u, v, td, tc);}dijkstra();dfs(s, -1);printf("%d", s);for(int i = 0; i < ans.size(); i++){printf(" %d", ans[i]);}printf(" %d %d", dis[d], minCost);return 0;
}