第七届山东省省赛C Proxy（最短路）-白红宇

第七届山东省省赛C Proxy（最短路）

阅读量：6868 次

发布时间：2019-06-26

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

题意：

给出n个点和一些单向边，问从0到n+1

如果不能到则输出-1

如果能一步到则输出0

否则输出第一个到达的节点

如果两条路距离相等，则输出较小的节点

思路：

赛场上从前向后扫然后又向前推的，，，特别别扭

回来之后想了下，可以建反向边，从n+1走到0记录前驱就好了

/* ***********************************************Author        :devilCreated Time  :2016/6/10 14:20:54************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;const int N=1010;const int inf=0x3f3f3f3f;struct node{ int v,d; node(int a=0,int b=0):v(a),d(b){} bool operator < (const node &a) const { return d>a.d; }};struct edge{ int v,cost; edge(int a=0,int b=0):v(a),cost(b){}};vector
                
                  eg[N];bool vis[N];int n,m,dis[N],pre[N];void dijkstra(int x){ memset(vis,false,sizeof(vis)); for(int i=0; i<=n+1; i++) dis[i]=inf; priority_queue
                 
                  q; while(!q.empty()) q.pop(); dis[x]=0; q.push(node(x,0)); node tmp; while(!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if(vis[u]) continue; vis[u]=1; for(int i=0; i
                  
                   dis[u]+cost) { dis[v]=dis[u]+cost; pre[v]=u; q.push(node(v,dis[v])); } else if(!vis[v]&&dis[v]==dis[u]+cost) pre[v]=min(pre[v],u); } }}int main(){ //freopen("in.txt","r",stdin); int t,u,v,w; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<=n+1;i++) eg[i].clear(); while(m--) { scanf("%d%d%d",&u,&v,&w); eg[v].push_back(edge(u,w)); } dijkstra(n+1); if(dis[0]==inf) { printf("-1\n"); continue; } if(pre[0]==n+1) { printf("0\n"); continue; } printf("%d\n",pre[0]); } return 0;}