全国企业信息官网网站,中国建设银行网上银行网站特点,WordPress建站步骤,手机分销网站公司问题描述 热心公益的G哥哥又来举办慈善晚会了#xff0c;这次他邀请到了巴菲特、马云等巨富#xff0c;还邀请到了大V、小C等算法界泰斗。晚会一共邀请了n位尊贵的客人#xff0c;每位客人都位于不同的城市#xff0c;也就是说每座城市都有且仅有一位客人。这些城市的编号为…问题描述 热心公益的G哥哥又来举办慈善晚会了这次他邀请到了巴菲特、马云等巨富还邀请到了大V、小C等算法界泰斗。晚会一共邀请了n位尊贵的客人每位客人都位于不同的城市也就是说每座城市都有且仅有一位客人。这些城市的编号为12...nG哥哥决定将晚会放在p城市举办。 城市之间有m条单向的交通路径两座城市间可能同时存在多条直接相连的路径通过每一条路的花费的金币为ti 。G哥哥十分慷慨大方决定为他的客人们报销了旅途中的花费。这些客人也都比较节俭因此他们会选择花费最少的路径往返p城市。其中有一些客人住在偏远的城市他们的城市与p城市之间没有直接或者间接能抵达的道路于是G哥哥决定从p城市派遣飞机去接送客人由于派遣的私人飞机比较豪华航空公司给出的价格一个人坐一次需要61109567金币并且G哥哥还要支付1000000000的油费。 G哥哥想知道客人中花费金币最多的人需要在路上花费多久金币。
输入格式 输出一行一个整数表示花费金币最多的客人所需的金币。
样例输入
4 7 2
1 3 2
3 4 4
4 2 3
1 4 7
1 2 4
2 3 5
3 1 2
样例输出
12
//本题的主要难点为:
//dijkstra(int start)对于有向图,求的是起点start-i的最短距离
//由于本题是有向图,一往一返需要跑两次dijkstra,分别求i-p和p-i
//此外还要注意到题目中提到的100000000061109567就是0x3f3f3f3f
//故极大值只能声明为0x3f3f3f3f,否则用其来初始化dist矩阵时会出错
#include bits/stdc.husing namespace std;const int N1050;
const int inf0x3f3f3f3f;//注意0x3f3f3f3f就是题目中的100000000061109567 struct Node//用于dijkstra算法的图结点类
{int nex;//邻接点 int weight;//边权 Node(){}Node(int n,int w)//构造函数 {nexn;weightw; } bool operator(const Node n)const//重载运算符用于堆排序 {if(weightn.weight)return nexn.nex;else return weightn.weight;}
};int n,m,p;
vectorNodeedge[N];
bool visit[N];//标记结点是否已访问
int dist1[N],dist2[N],dist3[N];void dijkstra(int start,int dist[])
//dijkstra算法求解起点start到所有结点的最短距离,结果存入dist数组
{memset(dist,0x3f,N*sizeof(int));//把数组当函数参数会退化成指针,sizeof(dist)只能得到1字节 memset(visit,0,sizeof(visit));//清空标记数组//以下是标准模板,省略注释 priority_queueNodepq;dist[start]0;pq.push(Node(start,dist[start]));while(!pq.empty()) {Node headpq.top();pq.pop();int nexhead.nex;int weighthead.weight;if(visit[nex])continue;visit[nex]true;for(const auto n:edge[nex]){if(dist[n.nex]dist[nex]n.weight){dist[n.nex]dist[nex]n.weight;pq.push(Node(n.nex,dist[n.nex]));}}}
}int main()
{scanf(%d%d%d,n,m,p);for(int i1;im;i)//m条有向边 {int u,v,t;scanf(%d%d%d,u,v,t);edge[u].push_back(Node(v,t)); } int ans0;for(int i1;in;i)//求i-p的最短路径 {dijkstra(i,dist1);//coutdist1[p] dist1[p]endl;dist3[i]dist1[p];//保存i到p的最短距离 }dijkstra(p,dist2);//求p-i的最短路径,dist2[i]即p到i的最短距离 for(int i1;in;i)//对每一名客人(结点) {ansmax(ans,dist3[i]dist2[i]);//比较往返过程中的最大花费 //附:若初始化的极大值inf不为0x3f3f3f3f,则在此句之前应该进行如下特判//if(dist3[i]inf)dist3[i]0x3f3f3f3f;//if(dist2[i]inf)dist2[i]0x3f3f3f3f;}printf(%d\n,ans);return 0;
}
