首页 > ACM题库 > HDU-杭电 > HDU 3655-Ensure No Absence[解题报告]HOJ
2014
11-30

HDU 3655-Ensure No Absence[解题报告]HOJ

Ensure No Absence

问题描述 :

In the year 2022, the scu acmers decide to hold a party, and most of the old scu acmers have recieved the invitation, including onmylove, tanlinghang, and zsasuke (the original members of the scu isap team).
As they graduated from scu ten years ago, they live in di erent cities currently. They are all very arrogant, and each believes himself to be the best runner among all the scu acmers. To prove this, they all decide to spend days running to the destination (the city where the party is to be held), and to save energy, they each will choose the shortest route for himself(there may exist more than one shortest routes, in such cases, they would choose one of them at random). But this lead to a series of problems: they may stop to rest occasionally, and once they meet each other on one same road, they will stop running and begin to argue for days who is the best runner, entirely forgetting the party.
The scu leaders are all very considerate, they don’t want the absence of anyone, so they will select a suitable city to hold the party to guarantee that the isap team members will not meet each other on their way to the party. But they are all very busy, so the task is assigned to you, brilliant icpcer!

输入:

Process till EOF.
Each case contains two positive integers n,m(3 ≤ n ≤ 3000; 1 ≤ m ≤ 200000) in the first line. Indicating the number of cities to choose from, and the number of the edges (onmylove lives in city 1, tanlinghang lives in city 2, and zsasuke, city 3), then m lines follow, each line contains 3 positive integers a, b, c (1 ≤ a, b ≤ n; 1 ≤ c ≤ 10; b ≠a, there is at most one edege between two distinct cities) indicating that it takes each of them(onmylove, tanlinghang, or zasuke) c days to get to city b from city a, or c days to get to city a from city b if running at full speed(from this, you know they all run at the same speed, so there is no point in arguing at all,but they are all very unreasonable!)

输出:

Process till EOF.
Each case contains two positive integers n,m(3 ≤ n ≤ 3000; 1 ≤ m ≤ 200000) in the first line. Indicating the number of cities to choose from, and the number of the edges (onmylove lives in city 1, tanlinghang lives in city 2, and zsasuke, city 3), then m lines follow, each line contains 3 positive integers a, b, c (1 ≤ a, b ≤ n; 1 ≤ c ≤ 10; b ≠a, there is at most one edege between two distinct cities) indicating that it takes each of them(onmylove, tanlinghang, or zasuke) c days to get to city b from city a, or c days to get to city a from city b if running at full speed(from this, you know they all run at the same speed, so there is no point in arguing at all,but they are all very unreasonable!)

样例输入:

3 2
1 2 1
2 3 1
4 3
1 4 2
2 4 1
3 4 3
5 5
1 5 2
4 5 2
5 2 3
2 4 5
3 4 1

样例输出:

1
2
1
4
1
5

Hint
In the first case, we could not choose city 3 to hold the party, since tanlinghang may rest on the road between 2 and 3, so onmylove may meet tanlinghang on the same road and fall into arguing. so we choose city 2 to hold the party.In the third case, we could not choose city 4 for the same reason. suppose we choose city 4, the shortest route for onmylove is 1-5-4, and the shortest route for tanlinghang is 2-5-4 or 2-4, if tanlinghang choose the route 2-5-4, he may meet onmylove on the road between 5 and 4, and arguing is inevitable.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>

using namespace std;
int const nMax=3010;
int const Mmax=200200*2;
int const inf=(1<<30);

int n,m;
int u[Mmax],v[Mmax],w[Mmax],next[Mmax];
int first[nMax];
int dist[nMax][4];
int vis[nMax];
queue<int> Q;

void spfa(int uu)
{
 int ca=uu;
 memset(vis,0,sizeof(vis));
 for(int i=1;i<=n;i++)dist[i][uu]=inf;
 dist[uu][uu]=0;
 vis[uu]=1;
 Q.push(uu);
 int vv;
 while(!Q.empty())
 {
 uu=Q.front();Q.pop();vis[uu]=0;
 // printf("dist[%d][%d]=%d\n",uu,ca,dist[uu][ca]);
 for(int e=first[uu];e!=-1;e=next[e]){
 vv=v[e];
 if(dist[vv][ca]>dist[uu][ca]+w[e]){
 dist[vv][ca]=dist[uu][ca]+w[e];
 if(!vis[vv]){
 Q.push(vv);
 vis[vv]=1;
 }
 }
 }
 }
 return ;
}

int b[nMax];
int main()
{
 while(scanf("%d%d",&n,&m)!=EOF)
 {
 int e=0;
 memset(first,-1,sizeof(first));
 for(int i=0;i<m;i++){
 scanf("%d%d%d",&u[e],&v[e],&w[e]);
 next[e]=first[u[e]];first[u[e]]=e;
 e++;
 u[e]=v[e-1];
 v[e]=u[e-1];
 w[e]=w[e-1];
 next[e]=first[u[e]];first[u[e]]=e;
 e++;
 }
 for(int i=1;i<=3;i++)
 spfa(i);
 memset(vis,0,sizeof(vis));
 m*=2;
 for(int e=0;e<m;e++){
 int ok=0;
 if(dist[u[e]][1]==dist[v[e]][1]+w[e])ok++;
 if(dist[u[e]][2]==dist[v[e]][2]+w[e])ok++;
 if(dist[u[e]][3]==dist[v[e]][3]+w[e])ok++;
 if(ok>1)vis[u[e]]=1;
 if(vis[u[e]]==0){

 for(int i=1;i<=3;i++){
 if(dist[u[e]][i]==inf){

 vis[u[e]]=1;
 break;
 }
 }
 }
 }
 int sum=0;
 for(int i=1;i<=n;i++)if(!vis[i]){
 for(int j=1;j<=3;j++){
 if(dist[i][j]==inf){

 vis[i]=1;
 break;
 }
 }
 
 if(!vis[i])
 b[sum++]=i;
 }
 if(sum==0)puts("impossible");
 else {
 printf("%d\n",sum);
 for(int i=0;i<sum;i++){
 if(i==0)printf("%d",b[i]);
 else printf(" %d",b[i]);
 }
 printf("\n");
 }
 }
 return 0;
}

  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示