最短路+是否经过指定的边

题目链接：https://ac.nowcoder.com/acm/contest/699/E
输入：
输入 n, s, t;
输入m
m条边。
输入k
k条边（边权=0）。

问：现在可以经过k条免费边的一条，求s到t的最短路是否要经过一条。如果经过输出Yes，和最小费用。否则输出No，和最小费用(1<=n, m, k<=1000)。

思路：把没有添加k条免费边的图跑一次最短路，费用：ans1。然后每次添加一条，并且删除上次添加的那条。跑最短路，费用：ans2=min(ans2, dijkstra(s, t))。

然后比较：ans1和ans2。

if(ans1>ans2)
    {
        printf("Yes\n");
        printf("%d\n",ans2);
    }
    else
    {
        printf("No\n");
        printf("%d\n",ans2);
    }

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=205;

vector< pair<int ,int > > e[maxn];
int n, m;
int dis[maxn];   //dis当前的最短路
int vis[maxn];   //是否已经求出最短路

priority_queue<pair<int, int> > q;
int dijkstra(int s, int t)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 3, sizeof(dis));
    while(!q.empty())
    {
        q.pop();
    }
    dis[s]=0;
    q.push(make_pair(-dis[s], s));
    while(!q.empty())
    {
        int now=q.top().second;                //一定是最短路上的顶点
        q.pop();
        if(vis[now])
        {
            continue;
        }
        vis[now]=1;
        for(int i=0;i<e[now].size();i++)       //访问所有的邻接点
        {
            int v=e[now][i].first;
            if(!vis[v]&&dis[v]>dis[now]+e[now][i].second)
            {
                dis[v]=dis[now]+e[now][i].second;
                q.push(make_pair(-dis[v], v));//把可能的最短路顶点加入队列
            }
        }
    }

    return dis[t];

}

int main()
{
    int s, t;
    scanf("%d%d%d",&n,&s,&t);
    scanf("%d",&m);

    int x, y, z;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back(make_pair(y ,z));
        e[y].push_back(make_pair(x ,z));
    }
    int ans1=dijkstra(s, t);
    int ans2=ans1;
    scanf("%d",&m);
    int u, v, uu, vv;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        if(i==0)
        {
            e[u].push_back(make_pair(v ,0));
            e[v].push_back(make_pair(u ,0));
            uu=u,vv=v;
        }
        else
        {
            e[uu].pop_back();
            e[vv].pop_back();
            e[u].push_back(make_pair(v ,0));
            e[v].push_back(make_pair(u ,0));
            uu=u,vv=v;
        }
        ans2=min(ans2, dijkstra(s, t));
    }
    if(ans1>ans2)
    {
        printf("Yes\n");
        printf("%d\n",ans2);
    }
    else
    {
        printf("No\n");
        printf("%d\n",ans2);
    }

    return 0;
}