#include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <cassert> #include <iostream> #include <algorithm> using namespace std; /*迪杰斯特拉算法为啥不能有负边 因为你要保证从队列中取出来的最小的点x一定是该节点到原点的最短距离 如果有负边，那么可能比他大的y点再加上负边导致x结点距离变得更小 这道题利用了迪杰斯特拉的思想 */ const int INF=0x3f3f3f3f; const int maxn=1000+10; int dis[maxn],vis[maxn]; struct Node { int v,value; Node() { } Node(int a,int b) { v=a; value=b; } bool operator<(const Node &d)const { return value<d.value; } }; vector<Node>G[maxn]; void dji() { priority_queue<Node> que; que.push(Node(1,INF)); while(!que.empty()) { Node node=que.top(); que.pop(); if(vis[node.v]) continue; vis[node.v]=1; int v=node.v; dis[v]=node.value; for(int i=0; i<G[v].size(); i++) { Node node1=G[v][i]; int v1=node1.v; if(vis[v1])continue; dis[v1]=max(dis[v1],min(dis[v],G[v][i].value)); que.push(Node(v1,dis[v1])); } } } int n,m; int main() { int t; scanf("%d",&t); int kase=0; while(t--) { scanf("%d%d",&n,&m); int a,b,c; memset(dis,0,sizeof dis); memset(vis,0,sizeof vis); for(int i=1;i<=n;i++)G[i].clear();//别忘了清除 for(int i=0; i<m; i++) { scanf("%d%d%d",&a,&b,&c); G[a].push_back(Node(b,c)); G[b].push_back(Node(a,c)); } dji(); if(n!=1) printf("Scenario #%d: %d ",++kase,dis[n]); else printf("Scenario #%d: 0 ",++kase); } return 0; }
#include <set>#include <map>#include <deque>#include <queue>#include <stack>#include <cmath>#include <ctime>#include <bitset>#include <cstdio>#include <string>#include <vector>#include <cstdlib>#include <cstring>#include <cassert>#include <iostream>#include <algorithm>
using namespace std;/*迪杰斯特拉算法为啥不能有负边 因为你要保证从队列中取出来的最小的点x一定是该节点到原点的最短距离 如果有负边，那么可能比他大的y点再加上负边导致x结点距离变得更小 这道题利用了迪杰斯特拉的思想*/const int INF=0x3f3f3f3f;const int maxn=1000+10;int dis[maxn],vis[maxn];struct Node{ int v,value; Node() {
} Node(int a,int b) { v=a; value=b; } bool operator<(const Node &d)const { return value<d.value; }};vector<Node>G[maxn];void dji(){ priority_queue<Node> que; que.push(Node(1,INF)); while(!que.empty()) { Node node=que.top(); que.pop(); if(vis[node.v]) continue; vis[node.v]=1; int v=node.v; dis[v]=node.value; for(int i=0; i<G[v].size(); i++) { Node node1=G[v][i]; int v1=node1.v; if(vis[v1])continue; dis[v1]=max(dis[v1],min(dis[v],G[v][i].value)); que.push(Node(v1,dis[v1])); } }
}int n,m;int main(){ int t; scanf("%d",&t); int kase=0; while(t--) { scanf("%d%d",&n,&m); int a,b,c; memset(dis,0,sizeof dis); memset(vis,0,sizeof vis); for(int i=1;i<=n;i++)G[i].clear(); for(int i=0; i<m; i++) { scanf("%d%d%d",&a,&b,&c); G[a].push_back(Node(b,c)); G[b].push_back(Node(a,c)); } dji(); if(n!=1) printf("Scenario #%d:
%d
",++kase,dis[n]); else printf("Scenario #%d:
0
",++kase); } return 0;}