HDU3790Dijkstra

原题 http://acm.hdu.edu.cn/showproblem.php?pid=3790

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 99999999
#define N 2000struct node{int d;//代表距离int p;//代表花费
}map[N][N];//必须要二维
int vis[N];
int dis[N];
int mon[N];
int n,m;void Dijkstra(int x){int i,j;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){dis[i] = map[x][i].d;mon[i] = map[x][i].p;}vis[x] = 1;int MIN1;int MIN2;int next;for(i=1;i<=n;i++){MIN1 = INF;MIN2 = INF;for(j=1;j<=n;j++){if(vis[j]==0 && ((dis[j]dis[next]+map[next][j].d) || (dis[j]==dis[next]+map[next][j].d && mon[j]>mon[next]+map[next][j].p))){dis[j] = dis[next]+map[next][j].d;mon[j] = mon[next]+map[next][j].p;}}}}int main(){int i,j;int a,b,cc,dd;int dx,dy;while(~scanf("%d%d",&n,&m)){if(n==0 && m==0)break;memset(mon,0,sizeof(mon));memset(dis,0,sizeof(dis));for(i=1;i<=n;i++){for(j=1;j<=n;j++){map[i][j].d = INF;map[i][j].p = INF;}}for(i=1;i<=n;i++){map[i][i].d = 0;map[i][i].p = 0;}for(i=1;i<=m;i++){scanf("%d%d%d%d",&a,&b,&cc,&dd);if(cc <= map[a][b].d){if(cc==map[a][b].d){if(dd < map[a][b].p){map[a][b].p = dd;map[b][a].p = dd;}}else if(cc < map[a][b].d){map[a][b].d = cc;map[b][a].d = cc;map[a][b].p = dd;map[b][a].p = dd;}}}scanf("%d%d",&dx,&dy);Dijkstra(dx);printf("%d %d\n",dis[dy],mon[dy]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！