撰写
Background
Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.
Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.
Problem
You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo’s place) to crossing n (the customer’s place). You may assume that there is at least one path. All streets can be travelled in both directions.
Input
The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.
Output
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line.
Sample Input
1
3 3
1 2 3
1 3 4
2 3 5
Sample Output
Scenario #1:
4
题意：与上一题相反，找到所有可能道路中的权值的最小值的最大值
题解：本来说上一题用了spfa，这题就用dijkstra，结果被安排的明明白白…
还可以用最大生成树解，但是我心态已经崩了…
代码：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include
<map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<string,pair<int,int> > pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1205;
const int MAXN =1205;
/*struct Edge{
int v;
double cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[maxn];
void addedge(int u,int v, int w){
E[u].push_back(Edge(v,w));
}
bool vis[maxn];
int cnt[maxn];
double dist[maxn];
bool spfa(int start,int n){
memset(vis,false,sizeof(vis));
rep(i,1,n)dist[i]=INF;
vis[start]=true;
dist[start]=0;
queue<int>que;
while(!que.empty())que.pop();
que.push(start);
memset(cnt,0,sizeof(cnt));
cnt[start]=1;
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=false;
rep(i,0,E[u].size()-1){
int v = E[u][i].v;
if(dist[v]>max(dist[u],E[u][i].cost)){
dist[v]=max(dist[u],E[u][i].cost);
if(!vis[v]){
vis[v]=true;
que.push(v);
}
}
}
}
return true;
}*/
struct Edge
{
int v;
int cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)dist[i]=0;
vis[start]=true;
dist[start]=INF;
queue<int>que;
while(!que.empty())que.pop();
que.push(start);
memset(cnt,0,sizeof(cnt));
cnt[start]=1;
while(!que.empty())
{
int u=que.front();
que.pop();
vis[u]=false;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if(dist[v]<min(dist[u],E[u][i].cost)) { dist[v]=min(dist[u],E[u][i].cost); if(!vis[v]) { vis[v]=true; que.push(v); if(++cnt[v]>n) //cnt[i]为入队列次数，用来判定是否存在负环回路
return false;
}
}
}
}
return true;
}
int main(){
int n,x,y,z,t,m;
int cnt = 0;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
rep(i,1,n)E[i].clear();
rep(i,1,m){
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
SPFA(1,n);
cout<<"Scenario #"<<++cnt<<":"<<endl;
printf("%d\n\n", dist[n]);
}
return 0;
}
WA
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<cstdio>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cmath>
#include<set>
#include
<map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<string,pair<int,int> > pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
/*const int MAXN = 1e3+10;
struct qnode{
int c;
int v;
qnode(int _v=0,int _c=0):v(_v),c(_c){
}
bool operator<(const qnode &r)const
{return c<r.c;}
};
struct Edge//边结构
{
int cost,v; //储存边以及权
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}//初始化？？？
};
vector<Edge>E[MAXN];
bool vis[MAXN];//标记数组
int dist[MAXN];//到i时的答案
void Dijkstra(int n, int start) //点的编号从1开始，n是点的个数，start是源点
{
memset(vis, false, sizeof(vis));//初始化标记数组
for(int i = 1; i <= n;i++)dist[i] = 0;//初始化距离数组
priority_queue<qnode>que;//创建定义的优先队列，类型为qnote
while(!que.empty()) que.pop();//清空队列（这里不明白为什么要清空，是赋了初值吗？那为什么要赋初值）
dist[start]=INF;//源点到源点的距离初始化为INF，以便于得出后续
que.push(qnode(start,dist[start]));//源点入队，距离为INF
qnode tmp;//qnode类型的中转变量
while(!que.empty()){//只要队列不为空，也可以看作每次出队都是一轮松弛
tmp=que.top();//将队列中d最大的赋给tmp
que.pop();//出队
int u = tmp.v;//方便后续的操作，令u=该点的序号
if(vis[u])continue;//如果已被标记，那么跳过
vis[u]=true;//标记
for(int i=0;i<E[u].size();i++){//循环u的下一点的个数次
int v=E[tmp.v][i].v;//v=（点u数组中的下一点）
int cost=E[u][i].cost; //cost = （点u数组中到下一点的距离）
if(!vis[v]&&dist[v]<min(dist[u],cost)){ //松弛操作
dist[v]=min(dist[u],cost);
que.push(qnode(v,dist[v]));//入队
}
}
}
}
void addedge(int u,int v,int w){
E[u].push_back(Edge(v,w));
}*/
const int maxn = 10010;
struct qnode{
int v;
int c;
qnode(int _v = 0, int _c = 0):v(_v),c(_c){}
//bool operator <(const qnode &r) const{
// return c<r.c;
//}
};
struct cmp{
//c大的优先
bool operator()(const qnode &x,const qnode &y){
return x.c<y.c;
}
};
struct Edge{
int v,cost;
Edge(int _v = 0, int _cost = 0):v(_v),cost(_cost){}
};
vector<Edge>E[maxn];
bool vis[maxn];
int dist[maxn];
void Dijkstra(int n, int start){
memset(vis,false,sizeof(vis));
for(int i = 1; i <= n; i++)dist[i] = 0;
priority_queue<qnode,vector<qnode>,cmp> que;
while(!que.empty())que.pop();
dist[start] = INF;
que.push(qnode(start,INF));
qnode tmp;
while(!que.empty()){
tmp=que.top();
//cout<<tmp.c<<endl;
que.pop();
int u = tmp.v;
if(vis[u])continue;
vis[u] = true;
rep(i,0,E[u].size()-1){
int v=E[tmp.v][i].v;
int cost=E[u][i].cost;
//cout<<cost<<endl;
if(!vis[v]&&dist[v]<min(dist[u],cost)){
dist[v] = min(dist[u],cost);
que.push(qnode(v,dist[v]));
}
}
}
}
void addedge(int u, int v, int w){
E[u].push_back(Edge(v,w));
}
int t,n,m;
int main(){
scanf("%d",&t);
int u,v,w;
rep(i,1,t){
scanf("%d%d",&n,&m);
rep(j,1,n)E[i].clear();
rep(j,1,m){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
Dijkstra(n,1);
printf("Scenario #%d:\n%d\n\n", i,dist[n]);
}
return 0;
}