本文共 673 字，大约阅读时间需要 2 分钟。

题目

答案

#include
   
    #include
    
     using namespace std;#define inf 0x3f3f3f3fint map[501][501],cost[501][501],dis[501],mcost[501],vis[501];int n,m,start,last;void init(){   	memset(map,inf,sizeof(map));	memset(cost,inf,sizeof(cost));	memset(vis,0,sizeof(vis));	for(int i=0;i
     
      >n>>m>>start>>last;	while(m--)	{   		int x,y,z,money;		cin>>x>>y>>z>>money;		map[x][y]=map[y][x]=z;		cost[x][y]=cost[y][x]=money;	}		for(int i=0;i
      
       mcost[pos]+cost[pos][i])			{   				mcost[i]=mcost[pos]+cost[pos][i];			}		}	}}int main(){   	init();	dijkstra();	cout<
       
        <<" "<
       
      
     
    
   

总结

这道题在传统的求最短路径的基础上增加了花费的判断，我们只需在每次更新时将mcost也随之更新即可