这道题是求最短路径，由于n最大可以为1000，而Floyd算法的复杂度为O(n³)，因此会超时，所以只能用Dijkstra算法，题目要求我们不仅求出最短路径，还要求出最短路径下的最少花费：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>using namespace std;const int N = 1000 + 10;
const int INF = INT_MAX;struct Edge{int to, length, price;Edge(int t, int l, int p): to(t), length(l), price(p){}
};struct Point{int number, distance;Point(int n, int d): number(n), distance(d){}bool operator<(const Point p) const{return distance > p.distance;}
};vector<Edge> graph[N];
int dis[N], cost[N];void Dijkstra(int s){priority_queue<Point> pq;dis[s] = 0;cost[s] = 0;pq.push(Point(s, dis[s]));while(!pq.empty()){int u = pq.top().number;pq.pop();for(int i = 0; i < graph[u].size(); i++){int v = graph[u][i].to;int d = graph[u][i].length;int p = graph[u][i].price;if((dis[v] == dis[u] + d && cost[v] > cost[u] + p) || (dis[v] > dis[u] + d)){dis[v] = dis[u] + d;cost[v] = cost[u] + p;pq.push(Point(v, dis[v]));}}}
}int main(){int n, m, a, b, d, p, s, t;while(scanf("%d%d", &n, &m) != EOF && n && m){memset(graph, 0, sizeof(graph));fill(dis, dis + n + 1, INF);fill(dis, dis + n + 1, INF);for(int i = 0; i < m; i++){scanf("%d%d%d%d", &a, &b, &d, &p);graph[a].push_back(Edge(b, d, p));graph[b].push_back(Edge(a, d, p));}scanf("%d%d", &s, &t);Dijkstra(s);printf("%d %d\n", dis[t], cost[t]);}return 0;
}