Shortest Path(思维，dfs)

Shortest Path

Accepts: 40

Submissions: 610

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

There are multiple test cases. The first line of input contains an integer

The first line contains two integer $10^5)(1≤n,m≤105) -- the number of vertices and the number of queries. The next line contains 6 integers a_1, b_1, a_2, b_2, a_3, b_3a1,b1,a2,b2,a3,b3 (1 le a_1,a_2,a_3,b_1,b_2,b_3 le n)(1≤a1,a2,a3,b1,b2,b3≤n), separated by a space, denoting the new added three edges are (a_1,b_1)(a1,b1), (a_2,b_2)(a2,b2), (a_3,b_3)(a3,b3).$

In the next $s_isi and t_iti (1 le s_i, t_i le n)(1≤si,ti≤n), denoting a query.$

The sum of values of $10^6106.$

7
题解：最短路，本来完全暴力的最短路，果断超时，最后听了大神的想法，是求加的那三条边的最短路；让每次给的u,v找u到那三个起点的距离与
d[v]的和与v-u找最小值；还是超时，先放着吧，明天再看；
今天看了下发现自己写的很有问题，哪有那么麻烦，直接dfs下就好了，其实就是个思维题，用图论肯定超了。。。
AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
const int INF=0x3f3f3f3f;
#define SI(x) scanf("%d",&x)
#define PI(x) printf("%d",x)
#define P_ printf(" ")
#define mem(x,y) memset(x,y,sizeof(x))
const int MAXN=1e5+100;
const int MOD=1e9+7;
typedef long long LL;
struct Dot{
    int x,y;
};
Dot dot[3];
int u,v;
LL ans;
int vis[3];
void dfs(int pos,int temp){
    if(temp+abs(v-pos)<ans)ans=temp+abs(v-pos);
    for(int i=0;i<3;i++){
        if(vis[i])continue;
        vis[i]=1;
        dfs(dot[i].y,temp+abs(pos-dot[i].x)+1);
        dfs(dot[i].x,temp+abs(pos-dot[i].y)+1);
        vis[i]=0;
    }
}
int main(){
    int T;
    SI(T);
    int N,M;
    while(T--){
        SI(N);SI(M);
        for(int i=0;i<3;i++)SI(dot[i].x),SI(dot[i].y);
        LL temp=0;
        vis[0]=vis[1]=vis[2]=0;
        for(int i=1;i<=M;i++){
            SI(u);SI(v);
            ans=abs(v-u);
            dfs(u,0);
            temp=(temp+ans*i)%MOD;
        }
        printf("%lld
",temp);
    }
    return 0;
}


我的超时代码：先不说超时了，这样情况都没考虑完全，都没考虑过好几条路的情况；再者这样肯定会超时了。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<map>
 7 #include<string>
 8 using namespace std;
 9 const int INF=0x3f3f3f3f;
10 #define SI(x) scanf("%d",&x)
11 #define PI(x) printf("%d",x)
12 #define P_ printf(" ")
13 #define mem(x,y) memset(x,y,sizeof(x))
14 const int MAXN=1e5+100;
15 const int MOD=1e9+7;
16 int head[MAXN<<1];
17 int vis[MAXN];
18 int n,m;
19 int d1[MAXN],d2[MAXN],d3[MAXN];
20 int d[MAXN];
21 struct Node{
22     int from,to,next;
23 };
24 Node dt[MAXN<<1];
25 int edgnum;
26 void add(int u,int v){
27     dt[edgnum].from=u;dt[edgnum].to=v;
28     dt[edgnum].next=head[u];
29     head[u]=edgnum++;
30 }
31 void dijkscra(int u){
32     mem(vis,0);
33     mem(d,INF);
34     d[u]=0;
35     while(true){
36         int k=-1;
37         for(int i=1;i<=n;i++){
38             if(!vis[i])if(k==-1||d[i]<d[k])k=i;
39         }
40         if(k==-1)break;
41         vis[k]=1;
42         for(int i=head[k];i!=-1;i=dt[i].next){
43             int u=dt[i].from,v=dt[i].to;
44             //printf("%d %d
",u,v);
45             d[v]=min(d[v],d[u]+1);
46         }
47     }
48 }
49 
50 /*
51 int temp;
52 void dfs(int u,int v,int t){
53     if(t>n)return;
54     if(u==v){
55         temp=min(temp,t);
56         return;
57     }
58     for(int i=head[u];i!=-1;i=dt[i].next){
59         dfs(dt[i].to,v,t+1);
60     }
61 }
62 */
63 int main(){
64     int T;
65     SI(T);
66     while(T--){
67         SI(n);SI(m);
68         int a1,a2,a3,b1,b2,b3;
69         edgnum=0;mem(head,-1);
70         for(int i=1;i<n;i++)add(i,i+1),add(i+1,i);
71         scanf("%d%d%d%d%d%d",&a1,&b1,&a2,&b2,&a3,&b3);
72         add(a1,b1);add(b1,a1);add(a2,b2);add(b2,a2);add(a3,b3);add(b3,a3);
73         __int64 ans=0;
74         dijkscra(a1);
75         for(int i=1;i<=n;i++)d1[i]=d[i];
76         dijkscra(a2);
77         for(int i=1;i<=n;i++)d2[i]=d[i];
78         dijkscra(a3);
79         for(int i=1;i<=n;i++)d3[i]=d[i];
80         
81         for(int i=1;i<=m;i++){
82             int u,v;
83             scanf("%d%d",&u,&v);
84             /*dijkscra(u);*/
85             int temp=min(min(abs(v-u),abs(u-a1)+d1[v]),min(abs(u-a2)+d2[v],abs(u-a3)+d3[v]));
86             //printf("%d
",temp);
87             ans=(ans+temp*i)%MOD;
88         }
89         printf("%I64d
",ans);
90     }
91     return 0;
92 }