//土尔逊Torson 编写于2023/07/07 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <queue> #include <climits> using namespace std; const int MAXN = 1001; const int INF = INT_MAX; //无穷设为很大的数 struct Edge13801 { int to; //终点 int length; //长度 int price; //花费 Edge13801(int t, int l, int p):to(t),length(l),price(p){} }; struct Point13801 { int number; //点的编号 int distance; //源点到该点距离 Point13801(int n,int d):number(n),distance(d){} bool operator<(const Point13801& p)const {//优先级队列一般是大的值在前通过重载 < 操作符实现 小的值在前 return distance > p.distance; //距离小的优先级高 } }; vector<Edge13801> graph13801[MAXN]; //邻接表实现的图 int dis13801[MAXN]; //源点到各点距离 int cost13801[MAXN]; //记录花费 void Dijkstra(int s) { priority_queue<Point13801> myPriorityQueue13801; dis13801[s] = 0; cost13801[s] = 0; myPriorityQueue13801.push(Point13801(s, dis13801[s])); while (!myPriorityQueue13801.empty()) { int u = myPriorityQueue13801.top().number;//离源点最近的点 myPriorityQueue13801.pop(); for (int i = 0; i < graph13801[u].size(); ++i) { int v = graph13801[u][i].to; int l = graph13801[u][i].length; int p = graph13801[u][i].price; if (dis13801[v] == dis13801[u] + l && cost13801[v] > cost13801[u] + p || dis13801[v] > dis13801[u] + l) { //注意松弛操作的条件变换 dis13801[v] = dis13801[u] + l; cost13801[v] = cost13801[u] + p; myPriorityQueue13801.push(Point13801(v, dis13801[v])); } } } return; } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0) { break; } memset(graph13801, 0, sizeof(graph13801)); //图的初始化 fill(dis13801, dis13801 + n + 1, INF); //距离初始化为无穷 fill(cost13801, cost13801 + n + 1, INF); //花费初始化为无穷 while (m--) { int from, to, length, price; scanf("%d%d%d%d", &from, &to, &length, &price); graph13801[from].push_back(Edge13801(to, length, price)); graph13801[to].push_back(Edge13801(from, length, price)); } int s, t; //起点与终点 scanf("%d%d", &s, &t); Dijkstra(s); printf("%d %d\n", dis13801[t], cost13801[t]); } system("pause"); return EXIT_SUCCESS; } // 64 位输出请用 printf("%lld")