HDU4725(The Shortest Path in Nya Graph)-白红宇

HDU4725(The Shortest Path in Nya Graph)

阅读量：5232 次

发布时间：2019-06-14

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

题目链接:

题目大意:首先输入n,m,c；n代表点数，m是额外的边，c是层与层之间的权值。然后接下来n个数分别表示第i个点属于哪个层（层与层之间可互通），然后m行，每行三个数　　　　　　　　x，y，v，表示点x到y权值为v求点1到点n的最短路。

题目思路:把每个层拆成两个点（点到相应层之间距离为0），注意是拆成两个点，原因很简单，如果只拆成一个点，那么如果点1属于1层，点2也属于1层，那么推出来1与2距离为0，　　　　结果错误，所以拆成两个点，前一个点代表入点（点到层），都一个代表出点（层到点），然后SPFA或者堆优化dijkstra就行。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #define lson root<<1,l,mid#define rson root<<1|1,mid+1,r#define fi first#define se second#define seg int root,int l,int r#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))#define Min(x,y) (x
                   
                    y?x:y)using namespace std;#define gamma 0.5772156649015328606065120#define MOD 1000000007#define inf 0x3f3f3f3f#define N 1000001#define maxn 300021typedef long long LL;typedef pair
                    
                      PII;int vis[maxn],d[maxn],head[maxn],n,m,ans;int a[maxn];struct Node{ int to,next,v; Node(){} Node(int a,int b,int c):to(a),next(b),v(c){}}node[N];int hcnt=0;void add(int x,int y,int v){ ///加边 node[hcnt]=Node(y,head[x],v); head[x]=hcnt++;}void spfa(){ mst(d,inf); d[1]=0; mst(vis,0); vis[1]=1; deque
                     
                      q; ///deque优化 q.push_back(1); while(!q.empty()){ int s=q.front();q.pop_front(); vis[s]=0; for(int i=head[s];~i;i=node[i].next){ int e=node[i].to; if(d[e]>d[s]+node[i].v){ d[e]=d[s]+node[i].v; if(!vis[e]){ if(!q.empty()&&d[e]

转载于:https://www.cnblogs.com/Kurokey/p/5467041.html

你可能感兴趣的文章