给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
Input 输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。 (1
#include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<cstring> #include<queue> #include<string> using namespace std; const int MAX = 1010; const int INF = 0x3f3f3f3f; bool used[MAX]; struct node{ int len; int cost; }e[MAX][MAX],dis[MAX];//利用临街矩阵存图，两个权值用结构体来存储，也可以用pair类型 int n,m,s,t; void Dijkstra(int a){ for(int i=1;i<=n;i++){//dis的初始化 dis[i].len = INF; dis[i].cost = INF; } memset(used,false,sizeof(used)); dis[a].len = 0;dis[a].cost = 0;//把起始点初始为0 while(true){ int v = -1; for(int i=1;i<=n;i++){ if(!used[i] && (v == -1 || (dis[i].len < dis[v].len) || (dis[i].len == dis[v].len && dis[i].cost < dis[v].cost))) v = i; } if(v == -1) break;//如果所有点都被使用过，就结束 used[v] = true; for(int i=1;i<=n;i++){ if(dis[i].len > dis[v].len + e[v][i].len){ dis[i].len = dis[v].len + e[v][i].len; dis[i].cost = dis[v].cost + e[v][i].cost; } else if(dis[i].len == dis[v].len + e[v][i].len && dis[i].cost > dis[v].cost + e[v][i].cost){ dis[i].len = dis[v].len + e[v][i].len; dis[i].cost = dis[v].cost + e[v][i].cost; } } } } int main(void){ while(scanf("%d %d",&n,&m) != EOF && n != 0 && m != 0){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i == j){ e[i][j].len = 0; e[i][j].cost = 0; } else{ e[i][j].len = INF; e[i][j].cost = INF; } } } int x,y,z,c; for(int i=1;i<=m;i++){ scanf("%d %d %d %d",&x,&y,&z,&c); //加if判断是防止两个点之间不止一条路的情况，毕竟有些题很坑。 if(e[x][y].len > z){ e[x][y].len = z; e[x][y].cost = c; e[y][x].len = z; e[y][x].cost = c; } else if(e[x][y].len == z && e[x][y].cost > c){ e[x][y].len = z; e[x][y].cost = c; e[y][x].len = z; e[y][x].cost = c; } } scanf("%d %d",&s,&t); Dijkstra(s); printf("%d %d\n",dis[t].len,dis[t].cost); } return 0; }由于这个题的数据是点远远小于边的个数，所以用堆优化反而不如单纯的Dijkstra快。。。，当然我这只是单纯的试试这种写法。 代码如下：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<queue> using namespace std; const int MAX_V = (int)1e3+10; //const int MAX_E = (int)2e5+10; const int INF = 0x3f3f3f3f; typedef pair<int,int> P; int V,E,S,T; struct Edge{ int to,len,cost; }e; P dis[MAX_V];//first代表len,second代表cost; struct Rule{//定义堆的排序规则，让长度最小的在堆顶，如果长度相等就让花费最小的在堆顶。 bool operator()(const Edge &a,const Edge &b){ if(a.len > b.len) return true;//这个与结构体的排序规则定义刚好相反. else if(a.len == b.len && a.cost > b.cost) return true; return false; } }; vector<Edge> G[MAX_V]; priority_queue<Edge,vector<Edge>,Rule >q; void Dijkstra(int a){ for(int i=1;i<=V;i++){//初始化dis dis[i].first = INF; dis[i].second = INF; } dis[a].first = 0;dis[a].second = 0; q.push((Edge){a,dis[a].first,dis[a].second}); while(!q.empty()){ Edge ex = q.top();q.pop();//取出堆顶 int v = ex.to; for(int i=0;i<G[v].size();i++){ e = G[v][i]; if(dis[e.to].first > dis[v].first + e.len){ dis[e.to].first = dis[v].first + e.len; dis[e.to].second = dis[v].second + e.cost; q.push((Edge){e.to,dis[e.to].first,dis[e.to].second}); } else if((dis[e.to].first == dis[v].first + e.len) && (dis[e.to].second > dis[v].second + e.cost)){ // dis[e.to].first = dis[v].first + e.len; dis[e.to].second = dis[v].second + e.cost; q.push((Edge){e.to,dis[e.to].first,dis[e.to].second}); } } } } int main(void){ while(scanf("%d %d",&V,&E) != EOF && V!=0 && E!=0){ int x,y,z,c; for(int i=1;i<=V;i++){ G[i].clear(); } for(int i=1;i<=E;i++){ scanf("%d %d %d %d",&x,&y,&z,&c);//邻接表的存图方式。 e.to = y;e.len = z;e.cost = c; G[x].push_back(e); e.to = x;G[y].push_back(e); } scanf("%d %d",&S,&T); Dijkstra(S); printf("%d %d\n",dis[T].first,dis[T].second); } return 0; }