sdut3562Proxy(迪杰斯特拉+反向建树)

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3562.html
1640: 题目 B Proxy
时间限制: 1 Sec 内存限制: 128 MB
提交: 5 解决: 2
[提交][状态][讨论版] [Edit] [TestData]
题目描述

由于GFW (Great Firewall)，我们不能直接访问很多网站，如Facebook、Twitter、YouTube等，

但在代理服务器和代理服务器的帮助下，我们可以很容易地访问这些网站。

您有多个代理服务器的列表，其中一些可以直接连接，而另一些则不能。

但是您可以通过其他代理服务器通过单向连接访问代理服务器。我们都知道，网络访问的滞后将决定我们对访问的感受。

你有一个非常智能的代理软件，一旦你选择了一个可直接访问的代理服务器，你就会发现你可以找到最慢的方法到达网站。

你知道每一个联系的滞后。你访问的滞后是你整个联系的全部滞后。您希望最小化访问延迟，您将选择哪个代理服务器?

输入

输入多个测试用例，

第一行是整数T (T <= 100)，表示测试用例的数量。

每个测试用例的第一行是两个整数N (0 <= N <= 1000)， M (0 <= M <= 20000)。

N是代理服务器的数量(从1到N)。0是你的电脑的标签，(N+1)是目标网站服务器的标签。

然后M行，每一行包含三个u, v, w (0 <= u, v <= N + 1, 1 <= w <= 1000)，表示u可以直接连接到v，滞后是w。

输出

对于每个测试用例，您将选择直接连接的代理服务器的一个整数。您只能选择直接从您的计算机连接的代理服务器。

如果有多个选择，您应该用最少的标签输出代理服务器。如果你不能以任何方式访问目标网站，输出“-1”(没有引号)。

如果你可以直接访问目标网站，而且延迟是最小的，输出“0”(没有引号)。

样例输入
4
3 6
0 1 10
1 2 1
2 4 4
0 3 2
3 2 1
3 4 7
2 4
0 2 10
0 1 5
1 2 4
2 1 7
1 3
0 2 1
0 1 2
1 2 1
1 3
0 2 10
0 1 2
1 2 1

样例输出
3
-1
0
1

思路：迪杰斯特拉 反向建树

#include<stdio.h>
#include<string.h>
#define N 1002
#define Min(a,b) a>b?b:a
#define INF 1000000
int dis[N],bj[N];
int mp[N][N];int n;
void djsk(int v)
{
    int i,j,k,min;
    for(i=0;i<=n;i++)
    dis[i]=mp[v][i];//初始化dis数组 dis[i]=5代表从起始点到i点的最短距离 
     dis[v]=0;// v 代表起始节点 自己到自己为0 
     bj[v]=1;// 标记 已找到短路 
      for(i=0;i<=n;i++)// i 代表已经找到的最短路条数 
      {
        min=INF;k=0; 
        for(j=0;j<=n;j++)//从未找到最短路径元素中找一个路径最短的 
        if(!bj[j]&&dis[j]<min)min=dis[j],k=j;
        bj[k]=1;// 标记 已找到短路 
         for(j=0;j<=n+1;j++)//用但前最短路节点更新未找到最短路的节点 
         if(!bj[j]&&dis[j]>(dis[k]+mp[k][j]))dis[j]=dis[k]+mp[k][j];
      }
}
int main()
{
    int T,m,i,j,u,v,w,ans;
    scanf("%d",&T);
    while(T--)
    {  memset(bj,0,sizeof(bj));
       scanf("%d%d",&n,&m);
        for(i=0;i<=n+1;i++)
        for(j=0;j<=n+1;j++)
         mp[i][j]=INF;
         for(i=0;i<=n+1;i++)mp[i][i]=0;
         for(i=1;i<=m;i++)
         {scanf("%d%d%d",&u,&v,&w);
           mp[v][u]=w;
         }
         djsk(n+1);
         if(dis[0]==INF)printf("-1\n");
         else
         { ans=INF; 
            for(i=1;i<=n+1;i++)
            if(dis[i]+mp[i][0]==dis[0]&&i<ans)ans=i;
             if(ans==n+1)printf("0\n");
             else printf("%d\n",ans);
         }
    }

return 0;
}

#include<stdio.h>
#include<string.h>
#define N 1002
#define Min(a,b) a>b?b:a
#define INF 1000000
int dis[N],s[2][N];
int mp[N][N];int n;
void djsk(int v)
{
 int i,j,k,min,q=0,d=0,c=0;
 for(i=0;i<=n;i++)
  s[c][q++]=i,dis[i]=mp[v][i];//初始化dis数组 dis[i]=5代表从起始点到i点的最短距离 
 dis[v]=0;// v 代表起始节点 自己到自己为0 
 while(q)//没有未找到最短路的元素
 {
 min=INF;k=-1; 
 for(j=0;j<q;j++)//从未找到最短路径元素中找一个路径最短的 
 if(dis[s[c%2][j]]<min)
 { min=dis[s[c%2][j]];
 if(k!=-1)s[(c+1)%2][d++]=k;
 k=s[c%2][j];
 }
 else s[(c+1)%2][d++]=s[c%2][j];
 if(q==d)break;//寻找无改变 则未联通
 for(j=0;j<d;j++)//用但前最短路节点更新未找到最短路的节点 
 if(dis[s[(c+1)%2][j]]>(dis[k]+mp[k][s[(c+1)%2][j]]))dis[s[(c+1)%2][j]]=dis[k]+mp[k][s[(c+1)%2][j]];
 c=(c+1)%2;q=d;d=0;//交换层次
 }
}
int main()
{
 int T,m,i,j,u,v,w,ans;
 scanf("%d",&T);
 while(T--)
 { 
 scanf("%d%d",&n,&m);
 for(i=0;i<=n+1;i++)
 for(j=0;j<=n+1;j++)
 mp[i][j]=INF;
 for(i=0;i<=n+1;i++)mp[i][i]=0;
 for(i=1;i<=m;i++)
 {scanf("%d%d%d",&u,&v,&w);
 mp[v][u]=w;
 }
 djsk(n+1);
 if(dis[0]==INF)printf("-1\n");
 else
 { ans=INF;
 for(i=1;i<=n+1;i++)
 if(dis[i]+mp[i][0]==dis[0]&&i<ans)ans=i;
 if(ans==n+1)printf("0\n");
 else printf("%d\n",ans);
 }
 }

return 0;
}