例题:hdu 3790
题目链接
题意概括
给出一个无向图,图中每个节点的权值有两个,一个是距离,一个是花费,求起点到终点的最短距离及其花费。
解题思路
这个题跟模板题的差距就是多了一个权值,首先需要知道的是,距离的权重比花费重要,所以在最短路的函数里面首先判断的是距离,当距离一样的时候在判断他的花费。最后求出最短距离及其花费。
代码:
#include#include #include #include #include #define inf 0x3f3f3f3fusing namespace std;int n,xx,yy;int line[1010][1010],vis[1010],dis[1010],pp[1010][1010],disp[1010];void prime(int x,int y) { int i,j,minn,k,minnp; memset(vis,0,sizeof(vis)); for(i=1; i<=n; i++) { dis[i]=line[x][i]; disp[i]=pp[x][i]; } vis[x]=1; for(j=1; j c) { line[a][b]=line[b][a]=c; pp[a][b]=pp[b][a]=d; } } scanf("%d%d",&a,&b); prime(a,b); printf("%d %d\n",xx,yy); } return 0;}