#include <iostream>#include <queue>#include <cstdio>#define INF 10000000
using namespace std;
struct node{ int dis,cost;};
struct path{ int value,cost;};
node lowcost[1005];bool inQueue[1005];path road[1005][1005];
int main(){ int N,M; while(scanf("%d%d",&N,&M),N!=0&&M!=0) { if(N==0 && M==0) break; for(int i=1;i<=N;i++) { inQueue[i]=false; lowcost[i].dis=INF; lowcost[i].cost=INF; for(int j=1;j<=N;j++) { road[i][j].cost=INF; road[i][j].value=INF; } } for(int i=1;i<=M;i++) { int s,e,v,c; scanf("%d%d%d%d",&s,&e,&v,&c); if(road[s][e].value>v)//图矩阵赋值，相连取距离最短，距离相同取费用最少 { road[s][e].value=v; road[s][e].cost=c; road[e][s].value=v; road[e][s].cost=c; } else if(road[s][e].value==v) { if(road[s][e].cost>c) { road[s][e].value=v; road[s][e].cost=c; road[e][s].value=v; road[e][s].cost=c; } } } int start,end; scanf("%d%d",&start,&end); queue<int> Q;//在这里用链表的好处就是后面进去的一定是后来发现的连通点 lowcost[start].dis=0;//start到自己的最小费用0 lowcost[start].cost=0; Q.push(start); inQueue[start]=true; while(!Q.empty()) { int temp=Q.front();//对每个与start可连通的点进行搜索 for(int i=1;i<=N;i++) { if(i!=temp&&i!=start) { if(lowcost[temp].dis+road[temp][i].value<lowcost[i].dis) //比较起点s到节点x+节点x到节点i的距离是否小于起点s直接到i从而找到一条s到i的最短路 见图片 { lowcost[i].dis=lowcost[temp].dis+road[temp][i].value; lowcost[i].cost=lowcost[temp].cost+road[temp][i].cost; if(inQueue[i]==false) { Q.push(i); inQueue[i]=true; } } else if(lowcost[temp].dis+road[temp][i].value==lowcost[i].dis) { if(lowcost[i].cost>road[temp][i].cost+lowcost[temp].cost) lowcost[i].cost=road[temp][i].cost+lowcost[temp].cost; } } } Q.pop(); inQueue[temp]=false; } if(lowcost[end].dis!=INF) printf("%d %d\n",lowcost[end].dis,lowcost[end].cost); else printf("0 0\n"); } return 0;}
================================哥是分割线=============================
以下是Dijstra算法
#include <math.h>#include <time.h>#include <stdio.h> #include <iostream>#include <fstream> #include <memory.h>#include <malloc.h>#include <vector>#include <queue>#include <stack> using namespace std;#define MAX_SIZE 1001#define MAX_NUM 10000000struct edge{ int d; int p;};edge cost[MAX_SIZE][MAX_SIZE];int choose(edge * distance,int n, int * found){ edge min={MAX_NUM,MAX_NUM}; int minpos=-1; for(int i=1;i<=n;i++) { if(!found[i]) { if(distance[i].d<min.d) { min=distance[i]; minpos=i; } else if(distance[i].d == min.d && distance[i].p<min.p) { min=distance[i]; minpos=i; } } } return minpos;}edge shotestpath(int v,int t,int n){ edge distance[MAX_SIZE]; int found[MAX_SIZE]; for(int i=1;i<=n;i++) { distance[i]=cost[v][i];//把每个节点i到初始节点s的距离和花费给distance found[i]=0; } found[v]=1; distance[v].d=0; distance[v].p=0; for(int i=1;i<n-1;i++) { int u=choose(distance,n,found); found[u]=1; if(u==t) { return distance[t]; } for(int w=1;w<=n;w++) { if(!found[w]) { if(distance[u].d+cost[u][w].d<distance[w].d) { distance[w].d=distance[u].d+cost[u][w].d; distance[w].p=distance[u].p+cost[u][w].p; } else if(distance[u].d+cost[u][w].d==distance[w].d && distance[u].p+cost[u][w].p<distance[w].p) { distance[w].d=distance[u].d+cost[u][w].d; distance[w].p=distance[u].p+cost[u][w].p; } } } } return distance[t];}int main(){ int n,m; //freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); while(scanf("%d%d",&n,&m) && n+m!=0) { for(int i=1;i<=n;i++)//节点初始化 { for(int j=1;j<=n;j++) { if(i==j) { cost[i][j].d=0; cost[i][j].p=0; } else { cost[i][j].d=MAX_NUM; cost[i][j].p=MAX_NUM; } } } int a,b,d,p; while(m--) { scanf("%d%d%d%d",&a,&b,&d,&p); if(cost[a][b].d>d)//以最小距离初始化节点间距离 { cost[a][b].d=cost[b][a].d=d; cost[a][b].p=cost[b][a].p=p; } else if(cost[a][b].d==d) { if(cost[a][b].p>p) cost[a][b].p=cost[b][a].p=p; } } int s,t; scanf("%d%d",&s,&t); edge e=shotestpath(s,t,n); if(e.d!=MAX_NUM) printf("%d %d\n",e.d,e.p); else printf("0 0\n"); } return 0;}
转载于:https://www.cnblogs.com/Skyxj/p/3178629.html
相关资源：数据结构—成绩单生成器