拯救公主计划

题目背景

“救命！”王宫的的守卫听到公主的惊呼，推开门冲进去发现恶龙掳走了公主……

题目描述

骑士回到王国发现公主被恶龙掳走了，骑士知道恶龙的巢穴在山谷 $y$ 点，而王国的位置在 $x$ 点。

拯救公主的路上有 $n$ 个补给点 ( 王国和恶龙巢穴也属于补给点 )，$n$ 个补给点由 $m$ 条双向道路连接起来，每条道路上都有一个恶龙的随从，每一个随从的战斗力不一定相同。

骑士虽然很焦急，但是他的战斗力是有限的，在找到恶龙前他并不希望遇到过于强大的敌人损耗自己的实力。所以请你规划一条从 $x$ 至 $y$ 的路线，使得经过的道路上的敌人的战斗力最大值最小。

输入格式

第一行有四个用空格隔开的 $n$，$m$，$x$，$y$，其含义见【题目描述】。

接下来 $m$ 行，每行三个整数 $u$, $v$, $w$,表示有一条道路连接补给点 $u$ 和补给点 $v$，且该道路上的敌人战斗力为 $w$。

两个补给点之间可能存在多条道路，不同道路上的敌人战斗力也可能不同。

输出格式

输出一行一个整数，代表骑士遇到的敌人中的最高战斗力。

样例 #1

样例输入 #1

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

样例输出 #1

2

提示

数据规模与约定

• 对于 $30\%$ 的数据， 保证 $n≤10$。
• 对于 $60\%$ 的数据， 保证 $n≤100$。
• 对于 $100\%$ 的数据， 保证 $1≤n≤10^4, 1≤m≤2×10^4, 1\le w≤10^4, 1≤x, y≤n$。且从 $x$ 补给点出发一定能到达 $y$ 补给点。

样例输入输出1解释

骑士要从1号补给点去4号补给点，最优路线为1->3->4

---

我的思路是dis[i]表示遇到的最小的补给点，

这是我的代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct edge{
    int v,w;
};
vector<pair<int ,int >> g[1000100];
long long INF = 2147483647;
long long dis[1001000];
bool vis[1001000];
void dijk(int s){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[s] = 0;
    for(int i =0;i < n;i++){
        int u = 0;
        for(int v = 1;v <= n;v++){
            if(!vis[v] && (u == 0 || dis[v]<dis[u]))u = v;
        }
        vis[u] = 1;
        for(int j = 0;j < g[u].size();j++){
            int v = g[u][j].first,w = g[u][j].second;
            if(w<dis[v]){
                dis[v] = w;
            }
        }
    }
}

int main(){
	int y;
    cin>>n>>m>>s>>y;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v ,w));
        g[v].push_back(make_pair(u ,w));
    }
    dijk(s);
    cout<<dis[y];  
    return 0;
}

但是，只AC 3个，Wa 5个