来源：牛客网
“一年一度的萤火夜跑活动来啦！！！",小贸听到这个消息后非常兴奋，对于一个天性活泼的小公主来说，这样的活动必须要参加还要争取拿到奖励，于是小贸迫不及待的去主办方摊位了解荧光夜跑的游戏规则:在整个校园里一共有n个站点，站点的编号从1到n，游戏规则是首先从1号站点出发，每个站点都可能获得去其他站点的门票，只有获得该站点到其他站点的门票才能从该站点移动到对应门票的站点(则表示该两站点相通)，相通的两个站点之间都有对应的路程距离，若两个站点之间不相通，则表示连站点之间的距离为正无穷，若小贸想走最短的距离从1号站点到达n号站点，则最短距离是多少，如果无法从 1号点走到 n 号点(即从1号点到n号点的距离)，则输出 impossible（这就是主办方的问题啦！！！）
输入描述:
第一行包含整数n和m 接下来m行每行包含三个整数x，y，z，表示存在一条从站点x到站点y的门票(即站点x和站点y之间是相通的),两站点之间的距离是z
输出描述:
输出一个整数，表示1号点到n号点的最短距离 如果路径不存在(从站点1到站点n的距离为正无穷)，则输出impossible
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e5+10;
int e[N][N];
int dis[N];
bool book[N];
int n,m;
int s;
struct node{
int to,w,next;
}edge[N];
int head[N];
int cnt;
void add(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void Dijkstra(){
for(int i=1;i<=n;i++)
dis[i]=e[s][i];
for(int i=1;i<=n;i++)
book[i]=0;
book[s]=1;
dis[s]=0;
for(int i=1;i<=n-1;i++){
int minDis=INF;
int k;
for(int j=1;j<=n;j++){
if(book[j]==0&&dis[j]<minDis){
minDis=dis[j];
k=j;
}
}
book[k]=1;
for(int j=1;j<=n;j++){
if(e[k][j]<INF){
if(dis[j]<dis[k]+e[k][j])
dis[j]=dis[k]+e[k][j];
}
}
}
}
int main(){
cin>>n>>m;
int u,v,w;
while(w--){
cin>>u>>v>>w;
add(u,v,w);
}
Dijkstra();
if(dis[n]==0x3f3f3f3f) cout<<"impossible";
else cout<<dis[n];
} 编译都不通过😭救救孩子
全部评论
(0) 回帖