CSP 交通规划201609-4-白红宇

CSP 交通规划201609-4

阅读量：4217 次

发布时间：2019-05-26

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

题目链接：

dijkstra + 记录数组 + 优先队列

这里千万不能加 if(cur == n) return;

注意：

（1）类型1：

当题目要求到 n的最短距离时候，可以使用cur == n结束（因为此时cur == n）表示did[n]已经确定

（2）类型2：

不仅仅是只求到n的最短距离，此时cur == n如果返回了，其它的临接点最短距离可能并未确定，

cur == n只是表示到n的最短距离确定了，此题就是要求到所有点都是最短距离前提下取，到某个点路径相同时候最小的前驱，因而不能cur == n直接就返回了。

#include
   
    #include
    
     #include
     
       #include
      
       #include
       
        #include
        
         using namespace std;#define INF 0x3f3f3f3f#define MAXN 10005 #define MAXM 100005typedef long long ll;struct Edge{ int to, w; Edge(){} Edge(int pto, int pw){ to = pto; w = pw; } bool operator < (const Edge o)const{ return w > o.w; }};int n,m;ll dis[MAXN];bool vis[MAXN];int pre[MAXN];//记录某点直接到达该点的最小长度vector
         
           adj[MAXN];priority_queue
          
            pq;void dijkstra(int s) { memset(vis,false,sizeof(vis)); memset(dis,INF,sizeof(dis)); memset(pre,INF,sizeof(pre)); dis[s] = 0; pre[s] = 0; pq.push(Edge(s,dis[s])); while(!pq.empty()){ Edge tmp = pq.top(); pq.pop(); int cur = tmp.to;// if(cur == n){ //不能有这个 // return ;// } if(vis[cur]) continue; vis[cur] = true; for(int i = 0; i < adj[cur].size(); ++i){ Edge e = adj[cur][i]; if(!vis[e.to]){ if(dis[e.to] > dis[cur] + e.w){ dis[e.to] = dis[cur] + e.w; pre[e.to] = e.w; pq.push(Edge(e.to,dis[e.to])); } else if(dis[e.to] == dis[cur] + e.w){//到某个点最短距离相同时候，取最小的前驱 pre[e.to] = min(e.w,pre[e.to]); } } } } }int main() { scanf("%d%d",&n,&m); int f,t,w; for(int i = 0; i < m; ++i){ scanf("%d%d%d",&f,&t,&w); adj[f].push_back(Edge(t,w)); adj[t].push_back(Edge(f,w)); } dijkstra(1); ll ans = 0; for(int i = 2; i <= n; ++i){ ans += pre[i]; } printf("%d",ans); return 0; }