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();
}