JD 1008：最短路径问题

本文主要是介绍JD 1008：最短路径问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ题目：click here~~

题目分析：无向图，每条边有长度和花费，求点s到t的最短路径长度和花费。若有相同的最短路径长度，找出最少的花费的那条。

邻接表 + Dijstra + 优先队列

AC_CODE

const int maxn = 1008 ;
const int inf = 1<<30 ;
vector<int> g[maxn] ;
int len[maxn][maxn] ;
int cost[maxn][maxn] ;
int dis[maxn] ;
int val[maxn] ;
int vis[maxn] ;
int s , t ;
typedef pair<int , int > pii ;
void bfs(){priority_queue<pii , vector<pii> , greater<pii> > que ;que.push(make_pair(0 , s)) ;while(!que.empty()){pii now = que.top() ; que.pop() ;int u = now.second ;vis[u] = 1 ;for(int i = 0;i < g[u].size();i++){int v = g[u][i] ;if(vis[v]) continue ;if(dis[v] > dis[u] + len[u][v]){dis[v] = dis[u] + len[u][v] ;val[v] = val[u] + cost[u][v] ;que.push(make_pair(dis[v] , v)) ;}else if(dis[v] == dis[u] + len[u][v] && val[v] > val[u] + cost[u][v]){val[v] = val[u] + cost[u][v] ;que.push(make_pair(dis[v] , v)) ;}}}
}int main(){int n , m , i , j , u , v , d , c;//freopen("in.txt","r",stdin) ;while(cin >> n >> m){if(n == 0 && m == 0) break ;for(i = 0;i < maxn;i++) g[i].clear() ;memset(len , 0 , sizeof(len)) ;memset(cost , 0 , sizeof(cost)) ;memset(vis , 0 , sizeof(vis)) ;fill(dis , dis + maxn , inf) ;fill(val , val + maxn , inf) ;for(i = 0;i < m;i++){scanf("%d%d%d%d",&u,&v,&d,&c) ;g[u].push_back(v) ;g[v].push_back(u) ;len[u][v] = len[v][u] = d ;cost[u][v] = cost[v][u] = c ;}scanf("%d%d",&s,&t) ;dis[s] = val[s] = 0 ;bfs() ;printf("%d %d\n",dis[t],val[t]) ;}
}

这篇关于JD 1008：最短路径问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---