Cod sursa(job #2171563)

Utilizator sebastiannrxRichiteanu Mihai Sebastian sebastiannrx Data 15 martie 2018 12:44:45
Problema Ubuntzei Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
#define inf 999999999
#define nn 2005
int cost,n,m,k,a[nn][nn],d[nn],v[50],vv[nn][nn];
bool s[nn],s2[50];
void read () {
    f>>n>>m>>k;
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
            a[i][j]=a[j][i]=inf;
    for (int i=1;i<=k;++i)
        f>>v[i];
    for (int i=1;i<=m;++i) {
        int x,y,z;
        f>>x>>y>>z;
        a[x][y]=a[y][x]=z;}}
void dijk (int x) {
    for (int i=1;i<=n;++i)
        d[i]=a[x][i],s[i]=0;
    s[x]=1;
    int kk;
    while (1) {
        int mi=inf;
        for (int i=1;i<=n;++i)
            if (!s[i] && mi>d[i]) {
                mi=d[i];
                kk=i;}
        if (mi==inf)
            break;
        s[kk]=1;
        for (int i=1;i<=n;++i)
            if (!s[i] && d[i]>mi+a[kk][i])
                d[i]=mi+a[kk][i];}
    for (int i=1;i<=n;++i)
        vv[x][i]=vv[i][x]=d[i];}
void go () {
    read();
    dijk(1);
    if (!k)
        g<<vv[1][n]<<'\n';
    else {
        for (int i=1;i<=k;++i)
            dijk(v[i]);
        for (int i=1;i<=n;++i)
            s[i]=0;
        v[++k]=n;
        int p=1;
        int nr=1;
        while (nr<=k) {
            int mi=inf;
            int kk=0;
            for (int i=1;i<=k;++i)
                if (!s[i] && vv[p][v[i]]<mi) {
                    mi=vv[p][v[i]];
                    kk=i;}
            cost+=mi;
            s[kk]=1;
            ++nr;
            p=v[kk];}
        g<<cost<<'\n';}}
int main()
{   go();
    return 0;
}