Dwarf Tower-白红宇

Dwarf Tower

阅读量：4699 次

发布时间：2019-06-09

本文共 1747 字，大约阅读时间需要 5 分钟。

骇人听闻的数据：

源代码：#include
     
      #include
      
       using namespace std;struct Node{    int T,X,Y;}Edge[100001];int n,m,i[10001];int main(){    scanf("%d%d",&n,&m);    for (int a=1;a<=n;a++)      scanf("%d",&i[a]);    for (int a=1;a<=m;a++)    {        scanf("%d%d%d",&Edge[a].T,&Edge[a].X,&Edge[a].Y);        i[Edge[a].T]=min(i[Edge[a].X]+i[Edge[a].Y],i[Edge[a].T]);    }    for (int a=m;a>=1;a--)      i[Edge[a].T]=min(i[Edge[a].X]+i[Edge[a].Y],i[Edge[a].T]);    printf("%d",i[1]);    return 0;}/*    AC就是AC了，没有理由。    数据水也不至于水到这种地步吧！*/

75分乱搞DFS：

源代码：#include
     
      #include
      
       #include
       
        using namespace std;struct Node{    int X,Y;    Node(int t1,int t2)    {        X=t1;        Y=t2;    }};vector 
        
          List[10001];int m,n,i[10001];bool Vis[10001]={
   0};void DFS(int t) //倒序记忆化DFS。{    Vis[t]=true;    int L=List[t].size();    for (int a=0;a

SPFA正解：

源代码：#include
     
      #include
      
       #include
       
        #include
        
         #define LL long longusing namespace std;struct Node{    LL X,Y;    Node(LL t1,LL t2)    {        X=t1;        Y=t2;    }};queue 
         
           Q;vector 
          
            List[10001];LL m,n,i[10001];bool In[10001];int main() //挺动脑子的一道题。{ scanf("%lld%lld",&n,&m); for (LL a=1;a<=n;a++) scanf("%lld",&i[a]); for (LL a=1;a<=m;a++) { LL t,t1,t2; scanf("%d%d%d",&t,&t1,&t2); List[t1].push_back(Node(t,t2)); List[t2].push_back(Node(t,t1)); } for (LL a=1;a<=n;a++) { Q.push(a); In[a]=true; } while (!Q.empty()) //可以朦朦胧胧地看做是某一个神秘点到节点的距离，转换成一个类似于SPFA的BFS，不断更新就好了。 { LL t=Q.front(); Q.pop(); In[t]=false; for (LL a=0;a