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

/*
limits:
1s
256M
*/

#include<iostream>
using namespace std;
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define endl "\n"
#define min(x,y) x>y?y:x
int n;
const int N = 50100;
struct Point{
    int x,y;
}pos[N];
int x1,x2,x3,x4,y1,y2,y3,y4;
void maintaince(Point t){
    if(t.x<x1){
        x2=x1,x1=t.x;
    }else if(t.x<x2){
        x2=t.x;
    }
    if(t.x>x4){
        x3=x4,x4=t.x;
    }else if(t.x>x3){
        x3=t.x;
    }
    if(t.y<y1){
        y2=y1,y1=t.y;
    }else if(t.y<y2){
        y2=t.y;
    }
    if(t.y>y4){
        y3=y4,y4=t.y;
    }else if(t.y>y3){
        y3=t.y;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("reduce.in","r",stdin);
    // freopen("reduce.out","w",stdout);
    cin>>n;
    x1=x2=y1=y2=N;
    x3=x4=y3=y4=-1;
    FOR(i,1,n){
        cin>>pos[i].x>>pos[i].y;
        maintaince(pos[i]);
    }
    int ans=(x4-x1)*(y4-y1);
    FOR(i,1,n){
        ans=min(ans,((pos[i].x==x1?x2:x1)-(pos[i].x==x4?x3:x4))*((pos[i].y==y1?y2:y1)-(pos[i].y==y4?y3:y4)));
    }
    cout<<ans<<endl;
}

 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

/*
limits:
2s
512M
*/
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int n,m,k;
int x,y,z;
const int maxn = 3*1e5+10,maxm = 1e6+10;
struct Edge{
    int to,next,w;
    // Edge(int x,int y,int z):to(x),next(y),w(z){    }
}edge[maxm];
int tot,head[maxm];
inline void addEdge(int u,int v,int w){
    edge[++tot]=(Edge){v,head[u],w};
    head[u]=tot;
}
int dis[maxn];
struct node{
    int u,d;
    bool operator < (const node &cp) const{
        return d>cp.d;
    }
};
priority_queue<node> q;
bool vis[maxn],need[maxn];
int dijkstra(int start){
    while(!q.empty()){
        q.pop();
    }
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    q.push((node){start,0});
    dis[start]=0;
    while(!q.empty()){
        int u=q.top().u;q.pop();
        if(need[u]&&u!=start){//就是想去这个点
            return dis[u];
        }
        if(!vis[u]){
            vis[u]=1;
            for(int i=head[u];i;i=edge[i].next){
                int v=edge[i].to,w=edge[i].w;
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    q.push((node){v,dis[v]});
                }
            }
        }
    }
    return 0x3f3f3f3f;
}
int main(){
    // freopen("tour1.in","r",stdin);
    // freopen("tour.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        addEdge(x,y,z);
    }
    for(int i=1;i<=k;i++){
        cin>>x;
        need[x]=1;
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        if(need[i]==1){
            ans=min(dijkstra(i),ans);
        }
    }
    cout<<ans<<endl;
}