首页 > 代码库 > 1992 聚会

1992 聚会

2024-10-07 15:18:39   215人阅读

1992 聚会

 

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 黄金 Gold
 
 
 
题目描述 Description

小S 想要从某地出发去同学k的家中参加一个party，但要有去有回。他想让所用的
时间尽量的短。但他又想知道从不同的点出发，来回的最短时间中最长的时间是多
少，这个任务就交给了你

输入描述 Input Description

第一行三个正整数n, m, k(n是节点个数，m是有向边的条数，k是参加聚会的地点
编号)( 1 ≤ n ≤ 1000 ,1 ≤ m ≤ 100,000)
第二行..m + 1行每行3个整数x，y，w 代表从x到y需要花w的时间 0<w<=100

输出描述 Output Description

输出从不同的节点出发的最短时间中最长的时间

样例输入 Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输出 Sample Output

10

数据范围及提示 Data Size & Hint
 1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 const int MAXN = 1010; 7  8 struct Edge{ 9     int to,w,nxt;10 }e[100100];11 12 int dis[MAXN];13 int diss[MAXN];14 int head[MAXN];15 bool vis[MAXN];16 queue<int>q;17 int n,m,k,cnt,ans;18 19 void add(int u,int v,int w)    //从u到v有一条长度是w的边 20 {21     ++cnt;22     e[cnt].to = v;23     e[cnt].w = w;24     e[cnt].nxt = head[u];25     head[u] = cnt;26 }27 28 void spfa(int k)29 {30     memset(dis,0x3f,sizeof(dis));31     memset(vis,0,sizeof(vis));32     while (!q.empty()) q.pop();33     dis[k] = 0;34     q.push(k);35     vis[k] = true;36     while (!q.empty())37     {38         int u = q.front();39         q.pop();40         for (int i=head[u]; i; i=e[i].nxt)41         {42             int v = e[i].to;43             int w = e[i].w;44             if (dis[v]>dis[u]+w)45             {46                 dis[v] = dis[u]+w;47                 if (!vis[v])48                 {49                     q.push(v);50                     vis[v] = true;51                 }52             }53         }54         vis[u] = false;55     }56 }57 58 int main()59 {60     scanf("%d%d%d",&n,&m,&k);61     for (int u,v,w,i=1; i<=m; ++i)62     {63         scanf("%d%d%d",&u,&v,&w);64         add(u,v,w);65     }66     spfa(k);67     for (int i=1; i<=n; ++i)68         diss[i] = dis[i];69     for (int i=1; i<=n; ++i)70     {71         if (i!=k) spfa(i);72         if (dis[k]<=10000000 && diss[i]<=10000000)ans = max(ans,dis[k]+diss[i]);73     }74     printf("%d",ans);75     return 0;76 }

 

1992 聚会


联系
我们