Proxy

Proxy

时间: 1ms        内存:128M

描述:

Because of the GFW (Great Firewall), we cannot directly visit many websites, such as Facebook, Twitter, YouTube, etc. But with the help of proxy and proxy server, we can easily get to these website.
    You have a list of several proxy servers, some of them can be connected directly but others can’t. But you can visit proxy servers through other proxy server by a one-way connection. 
    As we all know, the lag of internet visit will decide our feelings of the visit. You have a very smart proxy software which will find the least lag way to reach the website once you choose a directly reachable proxy server. 
    You know the lag of every connection. The lag of your visit is the all the lags in your whole connection. You want to minimize the lag of visit, which proxy server you will choose?

输入:

  Multiple test cases, the first line is an integer T (T <= 100), indicating the number of test cases.
The first line of each test case is two integers N (0 <= N <= 1000), M (0 <= M <= 20000). N is the number of proxy servers (labeled from 1 to N). 
0 is the label of your computer and (N+1) is the label of the server of target website.
Then M lines follows, each line contains three integers u, v, w (0 <= u, v <= N + 1, 1 <= w <= 1000), means u can directly connect to v and the lag is w.

输出:

  An integer in one line for each test case, which proxy server you will choose to connect directly. You can only choose the proxy server which can be connected directly from your computer.
If there are multiple choices, you should output the proxy server with the least label. If you can’t visit the target website by any means, output “-1” (without quotes). If you can directly visit the website and the lag is the least, output “0” (without quotes).

示例输入:

1
3 6
0 1 10
1 2 1
2 4 4
0 3 2
3 2 1
3 4 7

示例输出:

3

提示:

参考答案(内存最优[0]):

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <cmath>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 200010
#define Mod 10001
using namespace std;
int map[1005][1005],cost[1005][1005],vis[1005],dis[1005],n,m;
int p[MAXN],level[MAXN];
void dijkstra(int s)
{
    int i,j,min,v;
    memset(vis,0,sizeof(vis));
    for(i=0; i<=n+1; ++i)
    {
        dis[i]=map[s][i];
    }
    dis[s]=0;
    vis[s]=1;
    for(i=0; i<=n+1; ++i)
    {
        v=-1;
        min=INF;
        for(j=0; j<=n+1; ++j)
        {
            if(!vis[j]&&dis[j]<min)
            {
                min=dis[j];
                v=j;
            }
        }
        if(v==-1)
            break;
        vis[v]=1;
        for(j=0; j<=n+1; ++j)
        {
            if(!vis[j]&&map[v][j]<INF)
            {
                if(dis[j]>dis[v]+map[v][j])
                {
                    dis[j]=dis[v]+map[v][j];
                }
            }
        }
    }
}
int near[MAXN];
int main()
{
    int t,u,v,w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<=n+1; i++)
            for(int j=0; j<=n+1; ++j)
                map[i][j]=INF;
        int ne=0;
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            map[v][u]=w;
            if(u==0)
                near[ne++]=v;
        }
        dijkstra(n+1);
        if(dis[0]==INF)
        {
            printf("-1\n");
            continue;
        }
        sort(near,near+ne);
        int ans;
        for(int i=0; i<ne; ++i)
        {
            int u=near[i];
            if(dis[u]+map[u][0]==dis[0])
            {
                if(u==n+1)
                {
                    ans=0;
                    break;
                }
                ans=u;
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

参考答案(时间最优[0]):

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <cmath>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 200010
#define Mod 10001
using namespace std;
int map[1005][1005],cost[1005][1005],vis[1005],dis[1005],n,m;
int p[MAXN],level[MAXN];
void dijkstra(int s)
{
    int i,j,min,v;
    memset(vis,0,sizeof(vis));
    for(i=0; i<=n+1; ++i)
    {
        dis[i]=map[s][i];
    }
    dis[s]=0;
    vis[s]=1;
    for(i=0; i<=n+1; ++i)
    {
        v=-1;
        min=INF;
        for(j=0; j<=n+1; ++j)
        {
            if(!vis[j]&&dis[j]<min)
            {
                min=dis[j];
                v=j;
            }
        }
        if(v==-1)
            break;
        vis[v]=1;
        for(j=0; j<=n+1; ++j)
        {
            if(!vis[j]&&map[v][j]<INF)
            {
                if(dis[j]>dis[v]+map[v][j])
                {
                    dis[j]=dis[v]+map[v][j];
                }
            }
        }
    }
}
int near[MAXN];
int main()
{
    int t,u,v,w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<=n+1; i++)
            for(int j=0; j<=n+1; ++j)
                map[i][j]=INF;
        int ne=0;
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            map[v][u]=w;
            if(u==0)
                near[ne++]=v;
        }
        dijkstra(n+1);
        if(dis[0]==INF)
        {
            printf("-1\n");
            continue;
        }
        sort(near,near+ne);
        int ans;
        for(int i=0; i<ne; ++i)
        {
            int u=near[i];
            if(dis[u]+map[u][0]==dis[0])
            {
                if(u==n+1)
                {
                    ans=0;
                    break;
                }
                ans=u;
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注