D. Buy a Ticket(优先队列+dijkstra)-白红宇

D. Buy a Ticket(优先队列+dijkstra)

阅读量：5159 次

发布时间：2019-06-13

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

　　http://codeforces.com/problemset/problem/938/D

　　题意：n个城市，每个城市都要举办场演唱会，票价是a[i]，此外还有m条双向有权边连接各个城市，求从每个城市出发，看一场演唱会再返回的最小花费。

　　样例：in: 4 2　　　　　　　　out: 6 14 1 25　　　　　　　　　　

　　　　　　　1 2 4

　　　　　　　2 3 7

　　　　　　　6 20 1 25

　　　　　　　3 3　　　　　　　　　　 12 10 12

　　　　　　　1 2 1

　　　　　　　2 3 1

　　　　　　　1 3 1

　　　　　　　30 10 20

　　题解：这道题是多源最短路问题，可以用dijkstra和优先队列求解。

　　　　　首先将每个城市的票价加入优先队列，队列首是最便宜的城市票价，则不用去其他城市，从本城市花费就ok。然后从该城市开始扫离它最近的其他城市，然后其他城市的花费=min（其他城市的票费，第一个城市的票费加路费）（由于是优先队列，故输出的一定是该城市的最优解）。扫完存数组输出就ok了。

AC代码：　　

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
             9 #include
             
               10 #define inf int(0x3f3f3f3f) 11 #define pi acos(-1.0) 12 #define lson l,m,rt<<1 13 #define rson m+1,r,rt<<1|1 14 #define ll long long 15 #define MAXN 1000000 16 using namespace std; 17 18 ll n,m,num; 19 ll first[MAXN]; 20 ll ans[MAXN]; 21 bool vis[MAXN]; 22 23 struct Edge 24 { 25 ll id; 26 ll val; 27 ll next; 28 }e[MAXN]; 29 30 struct Node 31 { 32 ll id; 33 ll val; 34 35 } node[MAXN]; 36 37 priority_queue
              
               que; 38 39 bool operator <(Node a,Node b) 40 { 41 return a.val>b.val; 42 } 43 44 void add(ll a,ll b,ll c) 45 { 46 e[num].id=b; 47 e[num].val=c; 48 e[num].next=first[a]; 49 first[a]=num; 50 51 num++; 52 } 53 54 int main() 55 { 56 num=1; 57 fill(first,first+MAXN,-1); 58 59 scanf("%I64d%I64d",&n,&m); 60 ll a,b,c; 61 for(int i=1;i<=m;i++) 62 { 63 scanf("%I64d%I64d%I64d",&a,&b,&c); 64 add(a,b,c*2); 65 add(b,a,c*2); 66 } 67 68 for(int i=1;i<=n;i++) 69 { 70 scanf("%I64d",&node[i].val); 71 node[i].id=i; 72 que.push(node[i]); 73 } 74 75 while(!que.empty()) 76 { 77 Node cur=que.top(); 78 que.pop(); 79 80 if(vis[cur.id]) 81 continue; 82 83 vis[cur.id]=1; 84 ans[cur.id]=cur.val; 85 86 for(ll i=first[cur.id];i!=-1;i=e[i].next) 87 { 88 Node node1; 89 node1.id=e[i].id; 90 node1.val=e[i].val+cur.val; 91 que.push(node1); 92 } 93 } 94 95 for(int i=1;i<=n;i++) 96 { 97 printf("%I64d ",ans[i]); 98 } 99 100 101 return 0;102 }

转载于:https://www.cnblogs.com/reminito/p/8505183.html

你可能感兴趣的文章