QBSCHOOL - Đến trường

Tác giả: skyvn97

Ngôn ngữ: C++

#include<stdio.h>
#include<vector>
#include<queue>
#define MAX   5555
const int INF=1e9;
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int m,n;
vii g[MAX];
ll c[MAX];
int d[MAX];
int s,e;
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i,k,u,v,w;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&k);
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&w);
        g[u].push_back(ii(v,w));
        if (k==2) g[v].push_back(ii(u,w));
    }
    for (i=1;i<=n;i=i+1) {
        d[i]=INF;
        c[i]=0;
    }
    c[1]=1;
    d[1]=0;
}
void dijkstra(void) {
    int i,v,w;
    ii x;
    priority_queue<ii,vii,greater<ii> > q;
    q.push(ii(0,1));
    while (!q.empty()) {
        x=q.top(); q.pop();
        w=x.first;
        v=x.second;
        for (i=0;i<g[v].size();i=i+1) {
            if (d[g[v][i].first]==w+g[v][i].second) {
                c[g[v][i].first]+=c[v];
                continue;
            }
            if (d[g[v][i].first]>w+g[v][i].second) {
                d[g[v][i].first]=w+g[v][i].second;
                c[g[v][i].first]=c[v];
                q.push(ii(d[g[v][i].first],g[v][i].first));
                continue;
            }
        }
    }
    printf("%d %lld",d[n],c[n]);
}
int main(void) {
    loadgraph();
    dijkstra();
}

Download