1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
LL Get_Int(){
LL res=0,bj=1;char c=getchar();
while(!isdigit(c)){if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)){res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;
const int maxn=500005,maxm=1000005;
struct Edge {
int from,to;
LL dist;
int v;
bool operator < (const Edge& b) const {
return (v<b.v)||(v==b.v&&dist<b.dist);
}
} edge[maxm];
vector<Edge>edges[maxn];
void AddEdge(int x,int y,LL v,int l) {
edges[x].push_back((Edge) {
x,y,v,l
});
}
int n,m,s,t,father[maxn];
int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}
void Kruskal() {
sort(edge+1,edge+m+1);
for(int i=1; i<=n; i++)father[i]=i;
int cnt=0,Max=0;
for(int i=1; i<=m; i++) {
int fx=Get_Father(edge[i].from),fy=Get_Father(edge[i].to);
if(fx!=fy) {
if(Get_Father(s)!=Get_Father(t))Max=edge[i].v;
father[fx]=fy;
cnt++;
if(cnt==n-1)break;
}
}
for(int i=1; i<=m; i++)
if(edge[i].v<=Max) {
AddEdge(edge[i].from,edge[i].to,edge[i].dist,edge[i].v);
AddEdge(edge[i].to,edge[i].from,edge[i].dist,edge[i].v);
}
}
struct HeapNode {
LL d;
int u;
bool operator < (const HeapNode& b) const {
return d>b.d;
}
};
int vst[maxn],Max[maxn];
LL dist[maxn];
void Dijkstra() {
priority_queue<HeapNode>Q;
for(int i=1; i<=n; i++)dist[i]=1e18;
memset(vst,0,sizeof(vst));
dist[s]=0;
Q.push((HeapNode) {
0,s
});
while(!Q.empty()) {
int Now=Q.top().u;
Q.pop();
if(vst[Now])continue;
vst[Now]=1;
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(dist[Next]>dist[Now]+e.dist) {
dist[Next]=dist[Now]+e.dist;
Max[Next]=max(Max[Now],e.v);
Q.push((HeapNode) {
dist[Next],Next
});
}
}
}
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int(),t=Get_Int();
edge[i]=(Edge) {x,y,(LL)t*v,v};
}
s=Get_Int();
t=Get_Int();
Kruskal();
Dijkstra();
printf("%d %lld\n",Max[t],dist[t]);
return 0;
}
|
