codeforces 303 div2 E

赤裸裸的最短路，需要注意下枚举过程就好了。直接贴上别人的代码，发现他的代码挺符合我的风格，以后就这样写了。

#include <bits/stdc++.h>

using namespace std;

struct node{

    int y,z,id;

    node(){}

    node(int y,int z,int id):y(y),z(z),id(id){}

};

vector<node> e[];

int n,m,u;

int f[];

int ed[];

long long dis[];

vector<int> ans;

const long long inf = (long long)*;

int main(){

    cin >>n >>m;

    for (int i=;i<=m;i++){

        int x,y,z;

        cin >> x>>y>>z;

        ed[i]=z;

        e[x].push_back(node(y,z,i));

        e[y].push_back(node(x,z,i));

    }

    cin >> u;

    queue<int> q;

    q.push(u);

    for (int i=;i<=n;i++) dis[i]=inf;

    //for (int i=1;i<=n;i++) cout<<dis[i]<<endl;

    dis[u]=;

    while (!q.empty()){

        int now = q.front();

        q.pop();

        for (int i=;i<e[now].size();i++){

            int v = e[now][i].y;

            if (dis[now]+e[now][i].z<dis[v] || dis[now]+e[now][i].z==dis[v] && e[now][i].z<ed[f[v]]){

                f[v]=e[now][i].id;

                dis[v]=dis[now]+e[now][i].z;

                q.push(v);

            }

        }

    }

    long long cnt=;

    for (int i=;i<=n;i++)

        if (f[i]!=) cnt+=ed[f[i]],ans.push_back(f[i]);

    sort(ans.begin(),ans.end());

    cout << cnt<<endl;

    for(int i=;i<ans.size();i++){

        if (i>) cout<<" ";

        cout << ans[i];

    }

    return ;

}

巴特西

codeforces 303 div2 E

最新文章

热门文章