九度：题目1008：最短路径问题 - c++编程基础

题目描述：

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入：

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1

输出：

输出一行有两个数，最短距离及其花费。

样例输入：

样例输出：

9 11

分析：

乍一看像是dijkstra算法，但是还多了一个求最少花费的条件，所以不能找到目标点就返回，必须将所有能到目标点的情况都要遍历到，所以用SPFA算法

#include 
          
           
#include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; #define MAX 1002 #define INT 0x7fffffff int w[MAX]; int cost[MAX]; bool vis[MAX]; struct node{ int w,cost; }map[MAX][MAX]; int n,m,a,b,d,p,s,t; void SPFA(){ for(int i=1;i<=n;i++){w[i]=INT;cost[i]=INT;vis[i]=false;} queue
               
                 q; q.push(s); w[s]=0; cost[s]=0; vis[s]=true; while(!q.empty()){ int cur=q.front();q.pop(); vis[cur]=false; for(int i=1;i<=n;i++){ if(map[cur][i].w!=INT&&w[i]>=w[cur]+map[cur][i].w){ w[i]=w[cur]+map[cur][i].w; cost[i]=min(cost[i],cost[cur]+map[cur][i].cost); if(!vis[i]){ vis[i]=true; q.push(i); } } } } } int main(){ //freopen("C:\\in.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ if(!n&&!m)break; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){map[i][j].w=INT;map[i][j].cost=INT;} for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&a,&b,&d,&p); map[a][b].w=map[b][a].w=d; map[a][b].cost=map[b][a].cost=p; } scanf("%d%d",&s,&t); SPFA(); printf("%d %d\n",w[t],cost[t]); } return 0; } /************************************************************** Problem: 1008 User: starcuan Language: C++ Result: Accepted Time:10 ms Memory:9376 kb ****************************************************************/